{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Edge Weight Equilibrium Queries in a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #graph #array #strongly-connected-component"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #图 #数组 #强连通分量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperationsQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #边权重均等查询"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一棵由 <code>n</code> 个节点组成的无向树，节点按从 <code>0</code> 到 <code>n - 1</code> 编号。给你一个整数 <code>n</code> 和一个长度为 <code>n - 1</code> 的二维整数数组 <code>edges</code> ，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>]</code> 表示树中存在一条位于节点 <code>u<sub>i</sub></code> 和节点 <code>v<sub>i</sub></code> 之间、权重为 <code>w<sub>i</sub></code> 的边。</p>\n",
    "\n",
    "<p>另给你一个长度为 <code>m</code> 的二维整数数组 <code>queries</code> ，其中 <code>queries[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 。对于每条查询，请你找出使从 <code>a<sub>i</sub></code> 到 <code>b<sub>i</sub></code> 路径上每条边的权重相等所需的 <strong>最小操作次数</strong> 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>查询之间 <strong>相互独立</strong> 的，这意味着每条新的查询时，树都会回到 <strong>初始状态</strong> 。</li>\n",
    "\t<li>从 <code>a<sub>i</sub></code> 到 <code>b<sub>i</sub></code>的路径是一个由 <strong>不同</strong> 节点组成的序列，从节点 <code>a<sub>i</sub></code> 开始，到节点 <code>b<sub>i</sub></code> 结束，且序列中相邻的两个节点在树中共享一条边。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个长度为 <code>m</code> 的数组 <code>answer</code> ，其中 <code>answer[i]</code> 是第 <code>i</code> 条查询的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/11/graph-6-1.png\" style=\"width: 339px; height: 344px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]\n",
    "<strong>输出：</strong>[0,0,1,3]\n",
    "<strong>解释：</strong>第 1 条查询，从节点 0 到节点 3 的路径中的所有边的权重都是 1 。因此，答案为 0 。\n",
    "第 2 条查询，从节点 3 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 0 。\n",
    "第 3 条查询，将边 [2,3] 的权重变更为 2 。在这次操作之后，从节点 2 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 1 。\n",
    "第 4 条查询，将边 [0,1]、[1,2]、[2,3] 的权重变更为 2 。在这次操作之后，从节点 0 到节点 6 的路径中的所有边的权重都是 2 。因此，答案为 3 。\n",
    "对于每条查询 queries[i] ，可以证明 answer[i] 是使从 a<sub>i</sub> 到 b<sub>i</sub> 的路径中的所有边的权重相等的最小操作次数。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/11/graph-9-1.png\" style=\"width: 472px; height: 370px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]\n",
    "<strong>输出：</strong>[1,2,2,3]\n",
    "<strong>解释：</strong>第 1 条查询，将边 [1,3] 的权重变更为 6 。在这次操作之后，从节点 4 到节点 6 的路径中的所有边的权重都是 6 。因此，答案为 1 。\n",
    "第 2 条查询，将边 [0,3]、[3,1] 的权重变更为 6 。在这次操作之后，从节点 0 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 2 。\n",
    "第 3 条查询，将边 [1,3]、[5,2] 的权重变更为 6 。在这次操作之后，从节点 6 到节点 5 的路径中的所有边的权重都是 6 。因此，答案为 2 。\n",
    "第 4 条查询，将边 [0,7]、[0,3]、[1,3] 的权重变更为 6 。在这次操作之后，从节点 7 到节点 4 的路径中的所有边的权重都是 6 。因此，答案为 3 。\n",
    "对于每条查询 queries[i] ，可以证明 answer[i] 是使从 a<sub>i</sub> 到 b<sub>i</sub> 的路径中的所有边的权重相等的最小操作次数。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>1 &lt;= w<sub>i</sub> &lt;= 26</code></li>\n",
    "\t<li>生成的输入满足 <code>edges</code> 表示一棵有效的树</li>\n",
    "\t<li><code>1 &lt;= queries.length == m &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-edge-weight-equilibrium-queries-in-a-tree](https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-edge-weight-equilibrium-queries-in-a-tree](https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]]\\n[[0,3],[3,6],[2,6],[0,6]]', '8\\n[[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]]\\n[[4,6],[0,4],[6,5],[7,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        \n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w))\n",
    "            g[b].append((a, w))\n",
    "        \n",
    "        \n",
    "        freq = [[0] * 26 for _ in range(n)]\n",
    "        \n",
    "        q = [0]\n",
    "        vis = {0}\n",
    "        par = {0: -1}\n",
    "        while q:\n",
    "            new_q = []\n",
    "            for cur in q:\n",
    "                for nei, w in g[cur]:\n",
    "                    if nei in vis: continue\n",
    "                    par[nei] = cur\n",
    "                    new_p = freq[cur][:]\n",
    "                    new_p[w-1] += 1\n",
    "                    freq[nei] = new_p\n",
    "                    vis.add(nei)\n",
    "                    new_q.append(nei)\n",
    "            q = new_q\n",
    "        \n",
    "        @cache\n",
    "        def get_path(x):\n",
    "            if x == 0:\n",
    "                return [x]\n",
    "            return get_path(par[x]) + [x]\n",
    "        \n",
    "        def lca(a, b):\n",
    "            \n",
    "            pa, pb = get_path(a), get_path(b)\n",
    "            l, h = 0, min(len(pa), len(pb)) - 1\n",
    "            while l < h:\n",
    "                mid = l + (h - l + 1) // 2\n",
    "                if pa[mid] == pb[mid]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    h = mid - 1\n",
    "            return pa[l]\n",
    "            \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            ancestor = lca(a, b)\n",
    "            w = [0] * 26\n",
    "            for i in range(26):\n",
    "                w[i] = freq[a][i] + freq[b][i] - freq[ancestor][i] * 2\n",
    "            ans.append(sum(w) - max(w))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class LCA:\n",
    "    def __init__(self, g, root):\n",
    "        self.n = len(g)\n",
    "        self.root = root\n",
    "        self.num = (self.n).bit_length()\n",
    "        self.depth = [0] * self.n\n",
    "        self.parent = [[-1] * self.n for i in range(self.num)]\n",
    "\n",
    "        s = [root]\n",
    "        while s:\n",
    "            v = s.pop()\n",
    "            for u, _ in g[v]:\n",
    "                if u == self.parent[0][v]:\n",
    "                    continue\n",
    "                self.parent[0][u] = v\n",
    "                self.depth[u] = self.depth[v] + 1\n",
    "                s.append(u)\n",
    "\n",
    "        for k in range(self.num - 1):\n",
    "            for v in range(self.n):\n",
    "                if self.parent[k][v] == -1:\n",
    "                    self.parent[k + 1][v] = -1\n",
    "                else:\n",
    "                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]\n",
    "\n",
    "    def getLCA(self, u, v):\n",
    "        if self.depth[u] > self.depth[v]:\n",
    "            u, v = v, u\n",
    "        for k in range(self.num):\n",
    "            if ((self.depth[v] - self.depth[u]) >> k) & 1:\n",
    "                v = self.parent[k][v]\n",
    "        if u == v:\n",
    "            return u\n",
    "\n",
    "        for k in reversed(range(self.num)):\n",
    "            if self.parent[k][u] != self.parent[k][v]:\n",
    "                u = self.parent[k][u]\n",
    "                v = self.parent[k][v]\n",
    "        return self.parent[0][u]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(\n",
    "        self, n: int, edges: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        lca = LCA(g, 0)\n",
    "\n",
    "        q = len(queries)\n",
    "        ans = [math.inf] * q\n",
    "        lcas = [lca.getLCA(u, v) for u, v in queries]\n",
    "        for i in range(1, 27):\n",
    "            depth = [math.inf] * n\n",
    "            depth[0] = 0\n",
    "            stack = [0]\n",
    "            while stack:\n",
    "                u = stack.pop()\n",
    "                for v, w in g[u]:\n",
    "                    if depth[v] == math.inf:\n",
    "                        if w == i:\n",
    "                            depth[v] = depth[u]\n",
    "                        else:\n",
    "                            depth[v] = depth[u] + 1\n",
    "                        stack.append(v)\n",
    "            for i in range(q):\n",
    "                u, v = queries[i]\n",
    "                l = lcas[i]\n",
    "                ans[i] = min(depth[u] + depth[v] - 2 * depth[l], ans[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        path = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            path[u].append((v,w-1))\n",
    "            path[v].append((u,w-1))\n",
    "        lca = LCA(path, 0)\n",
    "        \n",
    "        # 记录每个节点对应路径上, 不同权值的边的数量\n",
    "        x = 26\n",
    "        vals = [[0]*x for _ in range(n)]\n",
    "        # DFS\n",
    "        st = [0]\n",
    "        while st:\n",
    "            u = st.pop()\n",
    "            for v,w in path[u]:\n",
    "                if v==lca.parent[0][u]: continue\n",
    "                for i in range(x):\n",
    "                    vals[v][i] = vals[u][i]\n",
    "                vals[v][w] += 1\n",
    "                st.append(v)\n",
    "        \n",
    "        ans = []\n",
    "        for a,b in queries:\n",
    "            l = lca.getLCA(a,b)\n",
    "            tmp = [0] * x\n",
    "            for i in range(x):\n",
    "                tmp[i] = vals[a][i] + vals[b][i] - 2*vals[l][i]\n",
    "            ans.append(sum(tmp) - max(tmp))\n",
    "        return ans\n",
    "\n",
    "class LCA:\n",
    "    def __init__(self, g, root) -> None:\n",
    "        self.n = len(g)\n",
    "        self.root = root\n",
    "        self.num = self.n.bit_length()  # 2^num >= n\n",
    "        self.depth = [0] * self.n       # 记录深度\n",
    "        # 记录 2^i 级祖先\n",
    "        self.parent = [[-1] * self.n for _ in range(self.num)]\n",
    "\n",
    "        # dfs 从root出发构成 parent, depth\n",
    "        s = [root]\n",
    "        while s:\n",
    "            v = s.pop()\n",
    "            for u,_ in g[v]:        # (u, w)\n",
    "                if u==self.parent[0][v]: continue\n",
    "                self.parent[0][u] = v\n",
    "                self.depth[u] = self.depth[v] + 1\n",
    "                s.append(u)\n",
    "        # 构建 2^i 级祖先\n",
    "        for k in range(self.num-1):\n",
    "            for v in range(self.n):\n",
    "                if self.parent[k][v] == -1:\n",
    "                    self.parent[k+1][v] = -1\n",
    "                else:\n",
    "                    self.parent[k+1][v] = self.parent[k][self.parent[k][v]]\n",
    "        \n",
    "    def getLCA(self, u,v):\n",
    "        \"\"\" 找到 u,v 的最近公共祖先, 复杂度 O(logn) \"\"\"\n",
    "        if self.depth[u] > self.depth[v]:\n",
    "            u,v = v,u\n",
    "        # 使得 u 和 v 在同一深度\n",
    "        for k in range(self.num):\n",
    "            if (self.depth[v] - self.depth[u]) >> k & 1:\n",
    "                v = self.parent[k][v]\n",
    "        # 二分查找 LCA\n",
    "        if u==v: return u\n",
    "        for k in range(self.num-1, -1, -1):\n",
    "            if self.parent[k][u] != self.parent[k][v]:\n",
    "                u = self.parent[k][u]\n",
    "                v = self.parent[k][v]\n",
    "        return self.parent[0][u]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(\n",
    "        self, n: int, edges: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w - 1))\n",
    "            g[v].append((u, w - 1))\n",
    "        q = collections.deque([0])\n",
    "        par = [0] * n\n",
    "        dep = [0] * n\n",
    "        summ = [None for _ in range(n)]\n",
    "        f = [[0] * 14 for _ in range(n)]\n",
    "        summ[0] = [0] * 26\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            f[u][0] = par[u]\n",
    "            for i in range(1, 14):\n",
    "                f[u][i] = f[f[u][i - 1]][i - 1]\n",
    "            for v, w in g[u]:\n",
    "                if par[u] != v:\n",
    "                    par[v] = u\n",
    "                    summ[v] = summ[u].copy()\n",
    "                    summ[v][w] += 1\n",
    "                    dep[v] = dep[u] + 1\n",
    "                    q.append(v)\n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            x, y = u, v\n",
    "            if dep[x] > dep[y]:\n",
    "                x, y = y, x\n",
    "            for i in reversed(range(14)):\n",
    "                if dep[y] - dep[x] >= 1 << i:\n",
    "                    y = f[y][i]\n",
    "            for i in reversed(range(14)):\n",
    "                if f[x][i] != f[y][i]:\n",
    "                    x, y = f[x][i], f[y][i]\n",
    "            if x != y:\n",
    "                x = par[x]\n",
    "            ans.append(\n",
    "                dep[u]\n",
    "                + dep[v]\n",
    "                - 2 * dep[x]\n",
    "                - max([summ[u][i] + summ[v][i] - 2 * summ[x][i] for i in range(26)])\n",
    "            )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LCA:\n",
    "    def __init__(self, g, root):\n",
    "        self.n = len(g)\n",
    "        self.root = root\n",
    "        self.num = (self.n).bit_length()\n",
    "        self.depth = [0]*self.n\n",
    "        self.parent = [[-1]*self.n for i in range(self.num)]\n",
    " \n",
    "        s = [root]\n",
    "        while s:\n",
    "            v = s.pop()\n",
    "            for u, _ in g[v]:\n",
    "                if u == self.parent[0][v]:\n",
    "                    continue\n",
    "                self.parent[0][u] = v\n",
    "                self.depth[u] = self.depth[v]+1\n",
    "                s.append(u)\n",
    " \n",
    "        for k in range(self.num-1):\n",
    "            for v in range(self.n):\n",
    "                if self.parent[k][v] == -1:\n",
    "                    self.parent[k+1][v] = -1\n",
    "                else:\n",
    "                    self.parent[k+1][v] = self.parent[k][self.parent[k][v]]\n",
    " \n",
    "    def getLCA(self, u, v):\n",
    "        if self.depth[u] > self.depth[v]:\n",
    "            u, v = v, u\n",
    "        for k in range(self.num):\n",
    "            if ((self.depth[v]-self.depth[u]) >> k) & 1:\n",
    "                v = self.parent[k][v]\n",
    "        if u == v:\n",
    "            return u\n",
    " \n",
    "        for k in reversed(range(self.num)):\n",
    "            if self.parent[k][u] != self.parent[k][v]:\n",
    "                u = self.parent[k][u]\n",
    "                v = self.parent[k][v]\n",
    "        return self.parent[0][u]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        path = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            path[u].append((v, w-1))\n",
    "            path[v].append((u, w-1))\n",
    "        lca = LCA(path, 0)\n",
    "        \n",
    "        parent = lca.parent[0]\n",
    "        x = 26\n",
    "        vals = [[0] * x for _ in range(n)]\n",
    "        stack = [0]\n",
    "        vis = [0] * n\n",
    "        vis[0] = 1\n",
    "        while stack:\n",
    "            u = stack.pop()\n",
    "            for v, w in path[u]:\n",
    "                if not vis[v]:\n",
    "                    vis[v] = 1\n",
    "                    stack.append(v)\n",
    "                    for i in range(x):\n",
    "                        # 统计\n",
    "                        vals[v][i] += vals[u][i]\n",
    "                    vals[v][w] += 1\n",
    "        \n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            l = lca.getLCA(u, v)\n",
    "            tmp = [0] * x\n",
    "            for i in range(x):\n",
    "                tmp[i] += vals[u][i] + vals[v][i] - vals[l][i] * 2\n",
    "            ans.append(sum(tmp) - max(tmp))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        neighbour = collections.defaultdict(dict)\n",
    "        for a, b, w in edges :\n",
    "            neighbour[a][b] = w\n",
    "            neighbour[b][a] = w\n",
    "        \n",
    "        # BFS to find the fathers & weight_counter\n",
    "        # depth 可以从 weight_counter 中得到\n",
    "        root = 0\n",
    "        to_visit = [[root, -1, [0]*27]]\n",
    "        fathers = [[-1] for _ in range(n)]\n",
    "        weight_counter = {0: [0]*27}\n",
    "        while len(to_visit) :\n",
    "            node, ft, wt = to_visit.pop(0)\n",
    "            for st in neighbour[node] :\n",
    "                if st == ft :\n",
    "                    continue\n",
    "                nwt = [t for t in wt]\n",
    "                nwt[neighbour[node][st]] += 1\n",
    "                fathers[st][0] = node\n",
    "                weight_counter[st] = nwt\n",
    "                to_visit.append([st, node, nwt])\n",
    "        \n",
    "        # Binary Lifting\n",
    "        for j in range(1, 15):\n",
    "            for i in range(n) :\n",
    "                if fathers[i][j-1] == -1 :\n",
    "                    new_f = -1\n",
    "                else :\n",
    "                    new_f = fathers[fathers[i][j-1]][j-1]\n",
    "                fathers[i].append(new_f)\n",
    "\n",
    "        def get_father(node, k) :\n",
    "            it = 0\n",
    "            while k > 0 :\n",
    "                if k % 2 == 1 :\n",
    "                    node = fathers[node][it]\n",
    "                it += 1\n",
    "                k = k // 2\n",
    "            return node\n",
    "        \n",
    "        # LCA\n",
    "        to_ret = []\n",
    "        for rpa, rpb in queries :\n",
    "            da = sum(weight_counter[rpa])\n",
    "            db = sum(weight_counter[rpb])\n",
    "            if da < db :\n",
    "                da, db = db, da\n",
    "                rpa, rpb = rpb, rpa\n",
    "            pa, pb = get_father(rpa, da-db), rpb\n",
    "            dt = db\n",
    "            while not fathers[pa][0] == fathers[pb][0] :\n",
    "                for i in range(15) :\n",
    "                    if not fathers[pa][i] == fathers[pb][i] :\n",
    "                        npa, npb = fathers[pa][i], fathers[pb][i]\n",
    "                    else :\n",
    "                        break\n",
    "                pa, pb = npa, npb\n",
    "            lca_t = fathers[pa][0] if not pa == pb else pa\n",
    "            wt = [weight_counter[rpa][i]+weight_counter[rpb][i]-2*weight_counter[lca_t][i] for i in range(27)]\n",
    "            to_ret.append(sum(wt)-max(wt))\n",
    "        return to_ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        if n == 1: return [0] * len(queries)\n",
    "        dc = defaultdict(list)\n",
    "        ndc = defaultdict(int)\n",
    "        for i,j,k in edges:\n",
    "            dc[i].append([j,k-1])\n",
    "            dc[j].append([i,k-1])\n",
    "            ndc[i] += 1\n",
    "            ndc[j] += 1\n",
    "        ndp = [i for i in ndc if ndc[i] == 1]\n",
    "        dp = []\n",
    "        while ndp:\n",
    "            ndp, dp = [], ndp\n",
    "            for i in dp:\n",
    "                for j,k in dc[i]:\n",
    "                    ndc[j] -= 1\n",
    "                    if ndc[j] == 1:\n",
    "                        ndp.append(j)\n",
    "        \n",
    "        root = dp[0]\n",
    "        flis = [0] * n\n",
    "        vlis = [[0] * 26] * n\n",
    "        fflis = [[] for _ in range(n)]\n",
    "        fdc = defaultdict(set)\n",
    "        fdc[0].add(root)\n",
    "        dp = [root]\n",
    "        ss = {root}\n",
    "        srt = 1\n",
    "        while dp:\n",
    "            ndp = []\n",
    "            for i in dp:\n",
    "                for j,k in dc[i]:\n",
    "                    if j not in ss:\n",
    "                        v0 = vlis[i][:]\n",
    "                        v0[k] += 1\n",
    "                        vlis[j] = v0\n",
    "                        flis[j] = srt\n",
    "                        fdc[srt].add(j)\n",
    "                        fflis[j].append(i)\n",
    "                        ss.add(j)\n",
    "                        ndp.append(j)\n",
    "            srt += 1     \n",
    "            dp = ndp\n",
    "        fflis[root].append(root)\n",
    "        m = int(math.log(max(fdc),2)) + 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                fflis[j].append(fflis[fflis[j][i]][i])\n",
    "        m += 1\n",
    "        def findgcd(a,b):\n",
    "            if flis[a] > flis[b]:\n",
    "                a, b = b, a\n",
    "            v = flis[a]\n",
    "            while flis[b] != v:                \n",
    "                srt = 1\n",
    "                while srt < m and flis[fflis[b][srt]] >= v:\n",
    "                    srt += 1\n",
    "                b = fflis[b][srt - 1]\n",
    "            while a != b:\n",
    "                for i in range(m):\n",
    "                    if fflis[a][i] == fflis[b][i]: break\n",
    "                if i <= 1:\n",
    "                    return fflis[a][i]\n",
    "                a, b = fflis[a][i-1], fflis[b][i-1]\n",
    "            return a\n",
    "        res = []\n",
    "        for i,j in queries:\n",
    "            g = findgcd(i,j)\n",
    "            mx = 0\n",
    "            for k in range(26):\n",
    "                mx = max(mx, vlis[i][k] + vlis[j][k] - 2 * vlis[g][k])\n",
    "            res.append(flis[i]+flis[j]-2*flis[g]-mx)\n",
    "        return res\n",
    "            \n",
    "                \n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class LCA:\n",
    "    def __init__(self, g, root,edges):\n",
    "        self.n = len(g)\n",
    "        self.root = root\n",
    "        self.num = (self.n).bit_length()\n",
    "        self.depth = [0]*self.n\n",
    "        self.parent = [[-1]*self.n for _ in range(self.num)]\n",
    "        self.dist =defaultdict(lambda :[0]*27)\n",
    " \n",
    "        s = [root]\n",
    "        while s:\n",
    "            v = s.pop()\n",
    "            #print(v,g)\n",
    "            for u in g[v]:\n",
    "                if u == self.parent[0][v]:\n",
    "                    continue\n",
    "                self.parent[0][u] = v\n",
    "                self.depth[u] = self.depth[v]+1\n",
    "                s.append(u)\n",
    "                self.dist[u] = [a+b for a,b in zip(self.dist[v] , edges.get((v,u)))] \n",
    " \n",
    "        for k in range(self.num-1):\n",
    "            for v in range(self.n):\n",
    "                if self.parent[k][v] == -1:\n",
    "                    self.parent[k+1][v] = -1\n",
    "                else:\n",
    "                    self.parent[k+1][v] = self.parent[k][self.parent[k][v]]\n",
    " \n",
    "    def getLCA(self, u, v):\n",
    "        if self.depth[u] > self.depth[v]:\n",
    "            u, v = v, u\n",
    "        for k in range(self.num):\n",
    "            if ((self.depth[v]-self.depth[u]) >> k) & 1:\n",
    "                v = self.parent[k][v]\n",
    "        if u == v:\n",
    "            return u\n",
    " \n",
    "        for k in reversed(range(self.num)):\n",
    "            if self.parent[k][u] != self.parent[k][v]:\n",
    "                u = self.parent[k][u]\n",
    "                v = self.parent[k][v]\n",
    "        return self.parent[0][u]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        path = [[] for _ in range(n)]\n",
    "        edgesDic = {}\n",
    "        for u, v, w in edges:\n",
    "            path[u].append(v)\n",
    "            path[v].append(u)\n",
    "            edgesDic[(u,v)]= edgesDic[v,u] = [1 if i==w else 0 for i in range(27) ]\n",
    "        lca = LCA(path, 0,edgesDic)\n",
    "        \n",
    " \n",
    "        ans = []\n",
    "        for a,b in queries:\n",
    "            c = lca.getLCA(a,b)\n",
    "            #print(c)\n",
    "            l1 = [a+b-c*2 for a,b,c in zip(lca.dist[a],lca.dist[b],lca.dist[c])]\n",
    "            ans.append(sum(l1)- max(l1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class LCA:\n",
    "    def __init__(self,root,g,edges={}):\n",
    "        self.n = len(g)\n",
    "        self.d =[0]*self.n\n",
    "        self.g=g\n",
    "        self.t = 20 # the 2**t layer depth of tree \n",
    "        self.f=[[0]*self.t for _ in range(self.n)]\n",
    "        self.dist=defaultdict(lambda :[0]*27)\n",
    "        self.edges =edges\n",
    "        self.bfs(root)\n",
    "        \n",
    "\n",
    "    def bfs(self,root):\n",
    "        st=deque([root])\n",
    "        self.d[root] =1\n",
    "        while st:\n",
    "            x = st.popleft()\n",
    "            for a in self.g[x]:\n",
    "                if self.d[a]: continue\n",
    "                self.d[a] = self.d[x] +1\n",
    "                self.dist[a] = [a+b for a,b in zip(self.dist[x] , self.edges.get((x,a)))] \n",
    "                self.f[a][0] = x\n",
    "                for j in range(1,self.t):\n",
    "                    self.f[a][j] = self.f[self.f[a][j-1]][j-1]\n",
    "                st.append(a)\n",
    "    \n",
    "    def lca(self,x,y):\n",
    "        if self.d[x]> self.d[y]:\n",
    "            x,y = y,x\n",
    "        for i in range(self.t-1,-1,-1):\n",
    "            if self.d[self.f[y][i]] >=self.d[x]:\n",
    "                y = self.f[y][i]\n",
    "        if x == y:\n",
    "            return x\n",
    "        for i in range(self.t-1,-1,-1):\n",
    "            if self.f[x][i] != self.f[y][i]:\n",
    "                x = self.f[x][i]\n",
    "                y = self.f[y][i]\n",
    "        return self.f[x][0]\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        g =[[] for _ in range(n+1)]\n",
    "        dicAg = {}\n",
    "        for a,b,c in edges:\n",
    "            a,b = a+1,b+1\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            dicAg[(a,b)]=dicAg[(b,a)]= [1 if i==c else 0 for i in range(27) ]\n",
    "        lca = LCA(1,g,dicAg)\n",
    "        res =[]\n",
    "        for a,b in queries:\n",
    "            a,b = a+1,b+1\n",
    "            c = lca.lca(a,b)\n",
    "            l1 = [a+b-c*2 for a,b,c in zip(lca.dist[a],lca.dist[b],lca.dist[c])]\n",
    "            res.append(sum(l1)- max(l1))\n",
    "            #print(a,b,c,lca.dist[a],lca.dist[b],lca.dist[c])\n",
    "            #print(l1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "\n",
    "        # 记录每个点的边\n",
    "        l_e = [[] for _ in range(n)]\n",
    "\n",
    "        for u, v, w in edges:\n",
    "            l_e[u].append((v, w))\n",
    "            l_e[v].append((u, w))\n",
    "\n",
    "        # 找到边最多的边作为中心点\n",
    "        size = 0\n",
    "\n",
    "        for i, es in enumerate(l_e):\n",
    "            if len(es) > size:\n",
    "                size = len(es)\n",
    "                o = i\n",
    "\n",
    "        # 记录每个点到o的w数量\n",
    "        l_w = [0] * n\n",
    "\n",
    "        # [到0的编号(o为-1)，到o的上层节点(o为-1)，层数(o为0)，w数量]\n",
    "        l_w[o] = -1, -1, 0, defaultdict(int)\n",
    "\n",
    "        dp = [(o, -1, 0)]\n",
    "\n",
    "        while dp:\n",
    "            u, p, no = dp.pop(0)\n",
    "\n",
    "            for i, (v, w) in enumerate(l_e[u]):\n",
    "                if v == p:\n",
    "                    continue\n",
    "\n",
    "                oi, _, no, d = l_w[u]\n",
    "                d = d.copy()\n",
    "                d[w] += 1\n",
    "                oi = i if oi == -1 else oi\n",
    "                l_w[v] = oi, u, no + 1, d\n",
    "\n",
    "                dp.append((v, u, no + 1))\n",
    "\n",
    "        # 计算返回值\n",
    "        # print(l_w)\n",
    "        ret = [0] * len(queries)\n",
    "\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            ia, _, noa, da = l_w[a]\n",
    "            ib, _, nob, db = l_w[b]\n",
    "\n",
    "            if ia != ib:\n",
    "                dp = defaultdict(int)\n",
    "            else:\n",
    "                # 先找到ab共同的p\n",
    "                while noa > nob:\n",
    "                    a = l_w[a][1]\n",
    "                    noa -= 1\n",
    "\n",
    "                while nob > noa:\n",
    "                    b = l_w[b][1]\n",
    "                    nob -= 1\n",
    "\n",
    "                while a != b:\n",
    "                    a = l_w[a][1]\n",
    "                    b = l_w[b][1]\n",
    "\n",
    "                dp = l_w[a][-1]\n",
    "\n",
    "            # a~b之间的w之间相加就行\n",
    "            d = da.copy()\n",
    "\n",
    "            for k, v in db.items():\n",
    "                d[k] += v - 2 * dp[k]\n",
    "\n",
    "            # 找到最大数量\n",
    "            num = 0\n",
    "            he = 0\n",
    "\n",
    "            for v in d.values():\n",
    "                he += v\n",
    "                num = max(num, v)\n",
    "\n",
    "            ret[i] = he - num\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class LowestCommonAncestor:\n",
    "    # https://cp-algorithms.com/graph/lca_binary_lifting.html\n",
    "    # https://leetcode.com/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/\n",
    "    def __init__(self, n: int, graph: List[List[int]], root=0):        \n",
    "        self.n = n\n",
    "        self.graph = graph\n",
    "        self.logn = math.ceil(math.log2(n))\n",
    "        self.depth = [-1 if i != root else 0 for i in range(n)]\n",
    "        self.parent = [[-1]*n for _ in range(self.logn)]\n",
    "        \n",
    "        # choose your own distance metric\n",
    "        self.distance = [[0]*26 for _ in range(n)]\n",
    "\n",
    "        self.dfs(root)\n",
    "        self.doubling()\n",
    "\n",
    "    def dfs(self, v, p=-1):\n",
    "        for e in self.graph[v]:\n",
    "            if e[0] == p: continue\n",
    "            self.parent[0][e[0]] = v\n",
    "            self.depth[e[0]] = self.depth[v] + 1\n",
    "            \n",
    "            # choose your own distance metric\n",
    "            self.distance[e[0]] = [x for x in self.distance[v]]\n",
    "            self.distance[e[0]][e[1]] += 1\n",
    "            \n",
    "            self.dfs(e[0], v)\n",
    "            \n",
    "    def doubling(self):\n",
    "        for i in range(self.logn-1):\n",
    "            for v in range(self.n):\n",
    "                if self.parent[i][v] != -1:\n",
    "                    self.parent[i+1][v] = self.parent[i][self.parent[i][v]]\n",
    "                    \n",
    "    def get(self, u, v):\n",
    "        if self.depth[u] > self.depth[v]: u, v = v, u\n",
    "        for i in range(self.logn):\n",
    "            if ((self.depth[v] - self.depth[u]) >> i) & 1:\n",
    "                v = self.parent[i][v]\n",
    "        if u == v:\n",
    "            return u\n",
    "        for i in range(self.logn-1, -1, -1):\n",
    "            if self.parent[i][u] != self.parent[i][v]:\n",
    "                u, v = self.parent[i][u], self.parent[i][v]\n",
    "        return self.parent[0][u]\n",
    "        \n",
    "    # choose your own distance metric\n",
    "    def distance_between(self, u, v):\n",
    "        lca = self.get(u, v)\n",
    "        return [x+y-2*z for x,y,z in zip(self.distance[u], self.distance[v], self.distance[lca])]\n",
    "\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        graphs = [[] for _ in range(n)]\n",
    "        \n",
    "        for a,b,c in edges:\n",
    "            c -= 1\n",
    "            graphs[a].append((b,c))\n",
    "            graphs[b].append((a,c))\n",
    "                    \n",
    "        trees = LowestCommonAncestor(n, graphs)\n",
    "        \n",
    "        allres = []\n",
    "        for a,b in queries:\n",
    "            minres = n-1\n",
    "            arr = trees.distance_between(a,b)\n",
    "            res = sum(arr) - max(arr)\n",
    "            allres.append(res)\n",
    "        \n",
    "        return allres\n",
    "                    \n",
    "                    \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        path_count = [None] * n\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append((v, w))\n",
    "            graph[v].append((u, w))\n",
    "        euler = []\n",
    "        first = [None] * n\n",
    "        def dfs(x, p, d, count):\n",
    "            path_count[x] = count[:]\n",
    "            first[x] = len(euler)\n",
    "            euler.append((x, d))\n",
    "            for b, w in graph[x]:\n",
    "                if b != p:\n",
    "                    count[0] += 1\n",
    "                    count[w] += 1\n",
    "                    dfs(b, x, d + 1, count)\n",
    "                    count[0] -= 1\n",
    "                    count[w] -= 1\n",
    "                    euler.append((x, d))\n",
    "        dfs(0, None, 0, [0] * 27)\n",
    "        st = [list(euler)]\n",
    "        L = 1\n",
    "        N = len(euler)\n",
    "        while L * 2 <= N:\n",
    "            nst = []\n",
    "            for i in range(N - 2 * L + 1):\n",
    "                nst.append(min(st[-1][i], st[-1][i + L], key=lambda x: x[1]))\n",
    "            st.append(nst)\n",
    "            L *= 2\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            start = first[a]\n",
    "            end = first[b]\n",
    "            start, end = min(start, end), max(start, end)\n",
    "            end += 1\n",
    "            k = (end - start).bit_length() - 1\n",
    "            p = min(st[k][start], st[k][end - (1 << k)], key=lambda x: x[1])[0]\n",
    "            total_count = [0] * 27\n",
    "            for i in range(27):\n",
    "                total_count[i] = path_count[a][i] + path_count[b][i] - path_count[p][i] * 2\n",
    "            ans.append(total_count[0] - max(total_count[1:]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for i,j,w in edges:\n",
    "            g[i].append((j,w))\n",
    "            g[j].append((i,w))\n",
    "        fa = [-1]*n\n",
    "        vis=[False]*n\n",
    "        intimestamp,outtimestamp=[0]*n,[0]*n\n",
    "        t = 0\n",
    "        ww = [ [0]*27 for _ in range(n)]\n",
    "        def dfs(x):\n",
    "            nonlocal t\n",
    "            t += 1\n",
    "            intimestamp[x] = t\n",
    "            for y,w in g[x]:\n",
    "                if not vis[y]:\n",
    "                    vis[y] = True \n",
    "                    fa[y] = x\n",
    "                    \n",
    "                    ww[y] = ww[x].copy()\n",
    "                    ww[y][w]  = ww[x][w] + 1\n",
    "\n",
    "                    dfs(y) \n",
    "            t += 1\n",
    "            outtimestamp[x] = t\n",
    "        vis[0] = True\n",
    "        dfs(0)\n",
    "\n",
    "        #最近公共祖先\n",
    "        def lca(x,y):\n",
    "            fx = x\n",
    "            while  fx !=-1:\n",
    "                if intimestamp[fx]<=intimestamp[y] and outtimestamp[fx]>=outtimestamp[y]:\n",
    "                    return fx\n",
    "                fx = fa[fx]\n",
    "            return 0\n",
    "        ans = []\n",
    "        # print(intimestamp,outtimestamp);print(ww)\n",
    "        for x,y in queries:\n",
    "            z = lca(x,y)\n",
    "            sum0,max0 = 0,0\n",
    "            for w in range(1,27):\n",
    "                max0 = max(max0,ww[x][w] - ww[z][w]  + ww[y][w] - ww[z][w])\n",
    "                sum0 +=  ww[x][w] - ww[z][w]  + ww[y][w] - ww[z][w]\n",
    "            ans.append( sum0 - max0 )\n",
    "        return ans\n",
    "\n",
    "\n",
    "        #树上前缀和"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for a, b, w in edges:\n",
    "            adj[a].append((b, w - 1))\n",
    "            adj[b].append((a, w - 1))\n",
    "\n",
    "        m = n.bit_length()\n",
    "        pa = [[-1] * m for _ in range(n)]\n",
    "        f = [[] for _ in range(n)] \n",
    "        # root = 0\n",
    "        def dfs(i, prev, cnt):\n",
    "            f[i] = cnt[:]\n",
    "            pa[i][0] = prev \n",
    "            for nxt, w in adj[i]:\n",
    "                if nxt != prev:\n",
    "                    cnt[w] += 1\n",
    "                    dfs(nxt, i, cnt)\n",
    "                    cnt[w] -= 1\n",
    "        \n",
    "        dfs(0, -1, [0] * 26)\n",
    "\n",
    "        # 倍增\n",
    "        for j in range(m - 1):\n",
    "            for i in range(n):\n",
    "                if pa[i][j] != -1:\n",
    "                    pa[i][j + 1] = pa[pa[i][j]][j]\n",
    "        \n",
    "        # LCA\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            res = [0] * 26\n",
    "            x = y = 0\n",
    "            for i in range(26):\n",
    "                res[i] = f[a][i] + f[b][i]\n",
    "                x += f[a][i]\n",
    "                y += f[b][i]\n",
    "            if x < y:\n",
    "                a, b = b, a\n",
    "                x, y = y, x\n",
    "\n",
    "            # same level\n",
    "            k = x - y\n",
    "            for i in range(k.bit_length()):\n",
    "                if (k >> i) & 1:\n",
    "                    a = pa[a][i]\n",
    "            \n",
    "            if a != b:\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    if pa[a][i] != pa[b][i]:\n",
    "                        a = pa[a][i]\n",
    "                        b = pa[b][i]\n",
    "                a = pa[a][0]\n",
    "\n",
    "            s = mx = 0\n",
    "            for i in range(26):\n",
    "                res[i] -= 2 * f[a][i]\n",
    "                s += res[i]\n",
    "                if res[i] > mx: mx = res[i]\n",
    "            ans.append(s - mx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeAncestor:\n",
    "    def __init__(self, edges: List[List[int]]):\n",
    "        n = len(edges) + 1\n",
    "        m = n.bit_length()\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:  # 节点编号从 0 开始\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        depth = [0] * n\n",
    "        pa = [[-1] * m for _ in range(n)]\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            pa[x][0] = fa\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    depth[y] = depth[x] + 1\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "\n",
    "        for i in range(m - 1):\n",
    "            for x in range(n):\n",
    "                if (p := pa[x][i]) != -1:\n",
    "                    pa[x][i + 1] = pa[p][i]\n",
    "        self.depth = depth\n",
    "        self.pa = pa\n",
    "\n",
    "    def get_kth_ancestor(self, node: int, k: int) -> int:\n",
    "        for i in range(k.bit_length()):\n",
    "            if (k >> i) & 1:  # k 二进制从低到高第 i 位是 1\n",
    "                node = self.pa[node][i]\n",
    "        return node\n",
    "\n",
    "    # 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）\n",
    "    def get_lca(self, x: int, y: int) -> int:\n",
    "        if self.depth[x] > self.depth[y]:\n",
    "            x, y = y, x\n",
    "        # 使 y 和 x 在同一深度\n",
    "        y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])\n",
    "        if y == x:\n",
    "            return x\n",
    "        for i in range(len(self.pa[x]) - 1, -1, -1):\n",
    "            px, py = self.pa[x][i], self.pa[y][i]\n",
    "            if px != py:\n",
    "                x, y = px, py  # 同时上跳 2**i 步\n",
    "        return self.pa[x][0]\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b, w in edges:\n",
    "            g[a].append((b, w - 1))\n",
    "            g[b].append((a, w - 1))\n",
    "        m = n.bit_length()\n",
    "        depth = [0] * n\n",
    "        nums = [[0] * 26 for _ in range(n)]\n",
    "        pa = [[-1] * m for _ in range(n)]\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            pa[x][0] = fa\n",
    "            for y, w in g[x]:\n",
    "                if y != fa:\n",
    "                    depth[y] = depth[x] + 1\n",
    "                    nums[y] = nums[x][:]\n",
    "                    nums[y][w] += 1\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "\n",
    "        for i in range(m - 1):\n",
    "            for x in range(n):\n",
    "                if (p := pa[x][i]) != -1:\n",
    "                    pa[x][i + 1] = pa[p][i]\n",
    "\n",
    "\n",
    "        def get_kth_ancestor(node: int, k: int) -> int:\n",
    "            for i in range(k.bit_length()):\n",
    "                if (k >> i) & 1:  # k 二进制从低到高第 i 位是 1\n",
    "                    node = pa[node][i]\n",
    "            return node\n",
    "\n",
    "        # 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）\n",
    "        def get_lca(x: int, y: int) -> int:\n",
    "            if depth[x] > depth[y]:\n",
    "                x, y = y, x\n",
    "            # 使 y 和 x 在同一深度\n",
    "            y = get_kth_ancestor(y, depth[y] - depth[x])\n",
    "            if y == x:\n",
    "                return x\n",
    "            for i in range(len(pa[x]) - 1, -1, -1):\n",
    "                px, py = pa[x][i], pa[y][i]\n",
    "                if px != py:\n",
    "                    x, y = px, py  # 同时上跳 2**i 步\n",
    "            return pa[x][0]\n",
    "\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            lca = get_lca(a, b)\n",
    "            maxx = 0\n",
    "            total = depth[a] + depth[b] - 2 * depth[lca]\n",
    "            for i in range(26):\n",
    "                maxx = max(maxx, nums[a][i] + nums[b][i] - 2 * nums[lca][i])\n",
    "            ans.append(total - maxx)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "'''\n",
    "问题简化后可以分为两个子问题：\n",
    "1. 找到uv两点间的链路并找出链路上权重出现最多的数字的次数，那么除此之外的边权都需要改；\n",
    "2. uv的链路 = (u到根0经过的边 - LCA到根0的边) + (v到根0经过的边 - LCA到根0的边)；\n",
    "\n",
    "由于边权只有26种可能，所以直接建表排查即可，不会是瓶颈，所以 找LCA 才是解题关键；\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        # 建父链，建深度表，建重子表，建子节点数量表\n",
    "        parent, depth, impNode, nodeCnt = [0] * n, [0] * n, [-1] * n, [1] * n\n",
    "        \n",
    "        # 建图\n",
    "        graph = [[] for _ in range(n)]\n",
    "        maxW = 0\n",
    "        for u,v,w in edges:\n",
    "            fw = w - 1\n",
    "            graph[u].append([v,fw])\n",
    "            graph[v].append([u,fw])\n",
    "            if maxW < w: maxW = w\n",
    "        \n",
    "        # 从0到指定节点的路径上，对应权重数值的数量\n",
    "        zeroW = [None] * n\n",
    "        zeroW[0] = [0] * maxW\n",
    "\n",
    "        # 建顶级父链，并查集入口\n",
    "        topParent = list(range(n))\n",
    "        def find(root: int) -> int:\n",
    "            if topParent[root] == root: return root\n",
    "            topParent[root] = find(topParent[root])\n",
    "            return topParent[root]\n",
    "\n",
    "        # 以0节点为根深搜并回溯完善父链、深度表、重子表、子节点数量表\n",
    "        def dfs(pre: int, cur: int, nextDepth: int):\n",
    "            impNodeCnt = 0\n",
    "            for nv, nw in graph[cur]:\n",
    "                if nv == pre: continue\n",
    "                zeroW[nv] = zeroW[cur].copy()\n",
    "                zeroW[nv][nw] += 1\n",
    "                depth[nv], parent[nv] = nextDepth, cur\n",
    "                dfs(cur, nv, nextDepth + 1)\n",
    "                nodeCnt[cur] += nodeCnt[nv]\n",
    "                if impNodeCnt < nodeCnt[nv]: impNodeCnt, impNode[cur] = nodeCnt[nv], nv\n",
    "            if impNodeCnt: topParent[impNode[cur]] = cur\n",
    "\n",
    "        dfs(-1, 0, 1)\n",
    "\n",
    "        # 答案计算\n",
    "        def combine(u: int, v: int, lca: int):\n",
    "            maxNum, total = 0, 0\n",
    "            for uw,vw,lcaw in zip(zeroW[u],zeroW[v],zeroW[lca]):\n",
    "                num = uw + vw - lcaw - lcaw\n",
    "                if maxNum < num: maxNum = num\n",
    "                total += num\n",
    "            return total - maxNum\n",
    "\n",
    "        # 寻找最近公共祖先\n",
    "        @cache\n",
    "        def lca(u: int, v: int) -> int:\n",
    "            if depth[find(u)] < depth[find(v)]: return lca(v, u)\n",
    "            if find(u) == find(v): return u if depth[u] < depth[v] else v\n",
    "            return lca(parent[find(u)], v)\n",
    "       \n",
    "        return [combine(u,v,lca(u,v)) for u,v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        RG = defaultdict(list)\n",
    "        for a,b,w in edges:\n",
    "            G[a].append((b,w))\n",
    "            G[b].append((a,w))\n",
    "        D = {};Deep = {}\n",
    "        vis = [0] * n;vis[0] = 1\n",
    "        def dfs(cur,d,V):\n",
    "            V = list(V)\n",
    "            D[cur] = V.copy();Deep[cur] = d\n",
    "            for nxt,w in G[cur]:\n",
    "                if vis[nxt]:continue\n",
    "                vis[nxt] = 1\n",
    "                V[w] += 1\n",
    "                RG[nxt] = cur \n",
    "                dfs(nxt,d+1,tuple(V))\n",
    "                V[w] -= 1\n",
    "            return d,V\n",
    "        dfs(0,1,tuple([0] * 27))\n",
    "        F = [[-1] * n for i in range(14)]\n",
    "        for i in range(1,n):\n",
    "            F[0][i] = RG[i]\n",
    "        for i in range(1,14):\n",
    "            for j in range(n):\n",
    "                F[i][j] = F[i-1][F[i-1][j]] if F[i-1][j] != -1 else -1\n",
    "        def lca(a,b):\n",
    "            da,db = Deep[a],Deep[b]\n",
    "            if da > db:\n",
    "                a,b,da,db = b,a,db,da\n",
    "            k = db-da;pos = 0\n",
    "            while k:\n",
    "                if k & 1:\n",
    "                    b = F[pos][b]\n",
    "                k >>= 1;pos += 1\n",
    "            def check(x):\n",
    "                pos = 0\n",
    "                A,B = a,b\n",
    "                while x:\n",
    "                    if x & 1:\n",
    "                        A = F[pos][A]\n",
    "                        B = F[pos][B]\n",
    "                    x >>= 1;pos += 1\n",
    "                return A == B\n",
    "            k = bisect_left(range(da),True,key = check);pos = 0\n",
    "            while k:\n",
    "                if k & 1:\n",
    "                    b = F[pos][b]\n",
    "                k >>= 1;pos += 1\n",
    "            return b\n",
    "\n",
    "        Res = []\n",
    "        for a,b in queries:\n",
    "            c = lca(a,b)\n",
    "            A,B,C = Deep[a],Deep[b],Deep[c]\n",
    "            mx = max([i+j-2*k for i,j,k in zip(D[a],D[b],D[c])])\n",
    "            Res.append(A+B-2*C-mx)\n",
    "        return Res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            graph[u].append((v,w))\n",
    "            graph[v].append((u,w))\n",
    "        \n",
    "        depth = [0 for _ in range(n)]\n",
    "        fa = [[0 for _ in range(16)] for _ in range(n)]\n",
    "        dis = [[0 for _ in range(27)] for _ in range(n)]\n",
    "\n",
    "        def dfs(u, p):\n",
    "            depth[u] = depth[p] + 1\n",
    "            fa[u][0] = p\n",
    "            for i in range(1, 16):\n",
    "                fa[u][i] = fa[fa[u][i-1]][i-1]\n",
    "\n",
    "            for v, w in graph[u]:\n",
    "                if v == p: continue\n",
    "                dis[v][0] = dis[u][0] + 1\n",
    "                for i in range(1, 27):\n",
    "                    dis[v][i] = dis[u][i] + (i == w)\n",
    "                dfs(v, u)\n",
    "\n",
    "        def lca(u, v):\n",
    "            if depth[u] < depth[v]: u, v = v, u\n",
    "\n",
    "            for i in range(15, -1, -1):\n",
    "                if depth[fa[u][i]] >= depth[v]:\n",
    "                    u = fa[u][i]\n",
    "            if u == v: return u\n",
    "            for i in range(15, -1, -1):\n",
    "                if fa[u][i] != fa[v][i]:\n",
    "                    u = fa[u][i]\n",
    "                    v = fa[v][i]\n",
    "            return fa[u][0]\n",
    "        \n",
    "        dfs(0, 0)\n",
    "\n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            a = lca(u, v)\n",
    "            cnt = 0\n",
    "            for i in range(1, 27):\n",
    "                cnt = max(cnt, dis[u][i] + dis[v][i] - 2*dis[a][i])\n",
    "            ans.append(dis[u][0] + dis[v][0] - 2*dis[a][0] - cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0] * len(queries)\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            neighbors[x].append((y, w - 1))\n",
    "            neighbors[y].append((x, w - 1))\n",
    "\n",
    "        query = [[] for _ in range(n)]\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            query[x].append((y, i))\n",
    "            query[y].append((x, i))\n",
    "        parent = list(range(n))\n",
    "        lca = [0] * len(queries)\n",
    "        road = [[0] * 26 for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "        def myFind(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = myFind(parent[x])\n",
    "            return parent[x]\n",
    "        def dfs(x, fa):\n",
    "            for y, w in neighbors[x]:\n",
    "                if y != fa:\n",
    "                    road[y] = road[x].copy()\n",
    "                    road[y][w] += 1\n",
    "                    depth[y] = depth[x] + 1\n",
    "                    dfs(y, x)\n",
    "                    parent[y] = x\n",
    "            for y, idx in query[x]:\n",
    "                if y == 0 or depth[y] > 0:\n",
    "                    lca[idx] = myFind(y)\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = []\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            cw = [0] * 26\n",
    "            for j in range(26):\n",
    "                cw[j] = road[x][j] + road[y][j] - 2 * road[lca[i]][j]\n",
    "            ans.append(sum(cw) - max(cw))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def tarjan_lca(graph, root, queries):\n",
    "    class UnionFindSet:\n",
    "        def __init__(self, n):\n",
    "            self.ps = [0] * n\n",
    "            for i in range(n):\n",
    "                self.ps[i] = i\n",
    "\n",
    "        def find(self, x):\n",
    "            p = x\n",
    "            while self.ps[p] != p:\n",
    "                p = self.ps[p]\n",
    "\n",
    "            while self.ps[x] != x:\n",
    "                up = self.ps[x]\n",
    "                self.ps[x] = p\n",
    "                x = up\n",
    "            return p\n",
    "\n",
    "        def set(self, x, p):\n",
    "            self.ps[x] = p\n",
    "\n",
    "    from collections import defaultdict\n",
    "    query_index = defaultdict(list)\n",
    "    ans = [-1] * len(queries)\n",
    "    for idx, (u, v) in enumerate(queries):\n",
    "        query_index[u].append((v, idx))\n",
    "        query_index[v].append((u, idx))\n",
    "\n",
    "    n = len(graph)\n",
    "    ufs = UnionFindSet(n)\n",
    "    visited = [0] * n\n",
    "\n",
    "    def dfs(root, parent):\n",
    "        # answer queries.\n",
    "        visited[root] = 1\n",
    "        query = query_index[root]\n",
    "        for v, idx in query:\n",
    "            if not visited[v]: continue\n",
    "            # 如果有对应的查询节点v, 并且这个节点之前访问过\n",
    "            # 那么使用这个节点的parent.\n",
    "            # 如果v是root的祖先节点的话，那么就是v\n",
    "            # 如果v在另外一个树上的话，那么就是最早交汇的节点\n",
    "            p = ufs.find(v)\n",
    "            ans[idx] = p\n",
    "\n",
    "        # continue to dfs.\n",
    "        for v, _ in graph[root]:\n",
    "            if v != parent:\n",
    "                dfs(v, root)\n",
    "                # 遍历子节点之后，将子节点的父节点设置为自己\n",
    "                ufs.set(v, root)\n",
    "\n",
    "    dfs(root, -1)\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for (u, v, w) in edges:\n",
    "            adj[u].append((v, w))\n",
    "            adj[v].append((u, w))\n",
    "        W = {}\n",
    "\n",
    "        def dfs(root, parent, weight):\n",
    "            W[root] = tuple(weight)\n",
    "            for v, w in adj[root]:\n",
    "                if v == parent: continue\n",
    "                weight[w] += 1\n",
    "                dfs(v, root, weight)\n",
    "                weight[w] -= 1\n",
    "\n",
    "        dfs(0, -1, [0] * 27)\n",
    "        lca = tarjan_lca(adj, 0, queries)\n",
    "        ans = []\n",
    "        for (u, v), r in zip(queries, lca):\n",
    "            w1 = list(W[u])\n",
    "            w2 = list(W[v])\n",
    "            w3 = list(W[r])\n",
    "            for i in range(27):\n",
    "                w1[i] -= w3[i]\n",
    "                w2[i] -= w3[i]\n",
    "                w1[i] += w2[i]\n",
    "            c = sum(w1) - max(w1)\n",
    "            ans.append(c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LCA:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.n = n\n",
    "        self.m = n.bit_length() + 1\n",
    "\n",
    "        self.depth = [float('inf') for _ in range(self.n)]\n",
    "        self.fa = [[-1 for _ in range(self.m)] for _ in range(self.n)]\n",
    "        self.graph = defaultdict(list)\n",
    "        self.child = defaultdict(list)\n",
    "    \n",
    "    def addedge(self, a, b):\n",
    "        self.graph[a].append(b)\n",
    "        self.graph[b].append(a)\n",
    "    \n",
    "    def bfs(self, root):\n",
    "        self.depth[root] = 0\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        for k in range(self.m):\n",
    "            self.fa[root][k] = root\n",
    "\n",
    "        while q:\n",
    "            k = len(q)\n",
    "            for _ in range(k):\n",
    "                cur = q.popleft()\n",
    "                for e in self.graph[cur]:\n",
    "                    if self.depth[e] > self.depth[cur] + 1:\n",
    "                        self.child[cur].append(e)\n",
    "                        self.depth[e] = self.depth[cur] + 1\n",
    "                        q.append(e)\n",
    "                        self.fa[e][0] = cur\n",
    "                        for i in range(1, self.m):\n",
    "                            self.fa[e][i] = self.fa[self.fa[e][i - 1]][i - 1]\n",
    "\n",
    "    def sol(self, a, b):\n",
    "        if self.depth[a] < self.depth[b]:\n",
    "            a, b = b, a\n",
    "        \n",
    "        for k in range(self.m - 1, -1, -1):\n",
    "            if self.depth[self.fa[a][k]] >= self.depth[b]:\n",
    "                a = self.fa[a][k]\n",
    "        if a == b:\n",
    "            return a\n",
    "        else:\n",
    "            for k in range(self.m - 1, -1, -1):\n",
    "                if self.fa[a][k] != self.fa[b][k]:\n",
    "                    a, b = self.fa[a][k], self.fa[b][k]\n",
    "        return self.fa[a][0]\n",
    "    \n",
    "    def routes(self, a, b):\n",
    "        p = self.sol(a, b)\n",
    "        aroute = []\n",
    "        cur = a\n",
    "        while cur != p:\n",
    "            aroute.append(cur)\n",
    "            cur = self.fa[cur][0]\n",
    "        broute = []\n",
    "        cur = b\n",
    "        while cur != p:\n",
    "            broute.append(cur)\n",
    "            cur = self.fa[cur][0]\n",
    "        \n",
    "        return aroute + [p] + broute\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        L = LCA(n)\n",
    "        cnt = [[0 for _ in range(27)] for _ in range(n)]\n",
    "        adj = defaultdict(lambda : defaultdict(list))\n",
    "        for u, v, w in edges:\n",
    "            L.addedge(u, v)\n",
    "            adj[u][v] = adj[v][u] = w\n",
    "        \n",
    "        L.bfs(0)\n",
    "\n",
    "        def dfs(node):\n",
    "            for o in L.child[node]:\n",
    "                cnt[o][adj[node][o]] += 1\n",
    "                for j in range(27):\n",
    "                    cnt[o][j] += cnt[node][j]\n",
    "                dfs(o)\n",
    "        \n",
    "        dfs(0)\n",
    "\n",
    "        res = []\n",
    "        for u, v in queries:\n",
    "            lca = L.sol(u, v)\n",
    "            check = [cnt[u][i] + cnt[v][i] - 2 * cnt[lca][i] for i in range(27)]\n",
    "            res.append(sum(check) - max(check))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def build_skip_list(graph_list, root_idx = 0):\n",
    "    N = len(graph_list)\n",
    "    ret = [None] * N\n",
    "    stack = []\n",
    "    def dfs(cur_idx, prev_idx):\n",
    "        n = len(stack)\n",
    "        L = 1\n",
    "        skip_list = []\n",
    "        while L <= n:\n",
    "            skip_list.append(stack[n-L])\n",
    "            L *= 2\n",
    "        ret[cur_idx] = skip_list, n\n",
    "        stack.append(cur_idx)\n",
    "        for nex_idx, _ in graph_list[cur_idx]:\n",
    "            if nex_idx != prev_idx:\n",
    "                dfs(nex_idx, cur_idx)\n",
    "        stack.pop()\n",
    "    dfs(root_idx, -1)\n",
    "    return ret\n",
    "\n",
    "def find_pow_index(num):\n",
    "    ret = []\n",
    "    i = 0\n",
    "    val = 1<<i\n",
    "    while val <= num:\n",
    "        if val & num:\n",
    "            ret.append(i)\n",
    "        i += 1\n",
    "        val <<= 1\n",
    "    return ret\n",
    "\n",
    "def find_common_ancestor(graph_skip_list, root_idx, i, j):\n",
    "    if graph_skip_list[i][1] < graph_skip_list[j][1]:\n",
    "        i, j = j, i\n",
    "    d = graph_skip_list[i][1] - graph_skip_list[j][1]\n",
    "    pow_indexs = find_pow_index(d)\n",
    "    while pow_indexs:\n",
    "        i = graph_skip_list[i][0][pow_indexs.pop()]\n",
    "    if i==j:\n",
    "        return j\n",
    "    k = len(graph_skip_list[i][0]) - 1\n",
    "    ret = root_idx\n",
    "    while k >= 0:\n",
    "        try:\n",
    "            graph_skip_list[i][0][k] == graph_skip_list[j][0][k]\n",
    "        except:\n",
    "            print((i, j, root_idx), k)\n",
    "            print(graph_skip_list[i])\n",
    "            print(graph_skip_list[j])\n",
    "            raise \n",
    "\n",
    "        if graph_skip_list[i][0][k] == graph_skip_list[j][0][k]:\n",
    "            ret = graph_skip_list[i][0][k]\n",
    "            k -= 1\n",
    "        else:\n",
    "            i = graph_skip_list[i][0][k]\n",
    "            j = graph_skip_list[j][0][k]\n",
    "            k = min(len(graph_skip_list[i][0]), k) - 1\n",
    "    return ret\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        graph_list = [[] for _ in range(n)]\n",
    "        for i, j, v in edges:\n",
    "            graph_list[i].append([j, v])\n",
    "            graph_list[j].append([i, v])\n",
    "        path_count_list = [dict() for _ in range(n)]\n",
    "        def dfs(i, j):\n",
    "            for k, v in graph_list[i]:\n",
    "                if k != j:\n",
    "                    path_count_list[k].update(path_count_list[i])\n",
    "                    path_count_list[k][v] = path_count_list[k].get(v, 0) + 1\n",
    "                    dfs(k, i)\n",
    "        root_idx = 0\n",
    "        graph_skip_list = build_skip_list(graph_list, root_idx = root_idx)\n",
    "        dfs(root_idx, -1)\n",
    "        #print(graph_skip_list)\n",
    "        #print(path_count_list)\n",
    "        ret = []\n",
    "        for i, j in queries:\n",
    "            if i == j:\n",
    "                ret.append(0)\n",
    "                continue\n",
    "            k = find_common_ancestor(graph_skip_list, root_idx, i, j)\n",
    "            tmp_dict = dict()\n",
    "            tmp_dict.update(path_count_list[i])\n",
    "            for key, val in path_count_list[j].items():\n",
    "                tmp_dict[key] = tmp_dict.get(key, 0) + val\n",
    "            for key, val in path_count_list[k].items():\n",
    "                if tmp_dict[key] == 2*val:\n",
    "                    tmp_dict.pop(key)\n",
    "                else:\n",
    "                    tmp_dict[key] -= 2*val\n",
    "            #print(i, j, k, tmp_dict)\n",
    "            ret.append(sum(tmp_dict.values()) - max(tmp_dict.values()))\n",
    "        return ret\n",
    "                 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 100018.边权重均等查询\n",
    "# https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/description/\n",
    "# lang=python\n",
    "\n",
    "\n",
    "# 解法:树上差分+找公共祖先+dfs\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        qs = [defaultdict(list) for _ in range(n)]\n",
    "        for idx, (u, v) in enumerate(queries):\n",
    "            qs[u][v].append(idx)\n",
    "            qs[v][u].append(idx)\n",
    "        \n",
    "        grid = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            grid[u].append((v, w - 1))\n",
    "            grid[v].append((u, w - 1))\n",
    "        \n",
    "        pa = list(range(n))\n",
    "        # i to tuple\n",
    "        i2t = dict()\n",
    "        ans = [0] * len(queries)\n",
    "        \n",
    "        def dfs(x, fa, w):\n",
    "            if fa == -1:\n",
    "                i2t[0] = (0,) * 26\n",
    "            else:\n",
    "                t = list(i2t[fa])\n",
    "                t[w] += 1\n",
    "                i2t[x] = tuple(t)\n",
    "            for y in qs[x]:\n",
    "                if y in i2t:\n",
    "                    z = y\n",
    "                    while pa[z] != z:\n",
    "                        z = pa[z]\n",
    "                    tmp = tuple(i + j - 2 * k for i, j, k in zip(i2t[x], i2t[y], i2t[z]))\n",
    "                    for idx in qs[x][y]:\n",
    "                        ans[idx] = sum(tmp) - max(tmp)\n",
    "            for zz, ww in grid[x]:\n",
    "                if zz != fa:\n",
    "                    dfs(zz, x, ww)\n",
    "            pa[x] = fa\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    import time\n",
    "    t0 = time.time()\n",
    "    \n",
    "    s = Solution()\n",
    "    func_name = dir(s)[-1]\n",
    "    func = getattr(s, func_name)\n",
    "    \n",
    "    print(func(n=7, edges=[[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 4, 2], [4, 5, 2], [5, 6, 2]],\n",
    "               queries=[[0, 3], [3, 6], [2, 6], [0, 6]]))\n",
    "    # 输出：[0,0,1,3]\n",
    "    print(func(n=8, edges=[[1, 2, 6], [1, 3, 4], [2, 4, 6], [2, 5, 3], [3, 6, 6], [3, 0, 8], [7, 0, 2]],\n",
    "               queries=[[4, 6], [0, 4], [6, 5], [7, 4]]))\n",
    "    # 输出：[1,2,2,3]\n",
    "    \n",
    "    t1 = time.time()\n",
    "    print(t1 - t0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        parent = [-1] * n\n",
    "        children = [[] for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "        count = [defaultdict(int) for _ in range(n)]\n",
    "        d = defaultdict(dict)\n",
    "        for x, y, w in edges:\n",
    "            d[x][y] = w\n",
    "            d[y][x] = w\n",
    "\n",
    "        def dfs(cur_index, cur_depth, pre_index):\n",
    "            depth[cur_index] = cur_depth\n",
    "            for nxt_index, weight in d[cur_index].items():\n",
    "                if nxt_index == pre_index:\n",
    "                    continue\n",
    "                parent[nxt_index] = cur_index\n",
    "                children[cur_index].append(nxt_index)\n",
    "                for k, v in count[cur_index].items():\n",
    "                    count[nxt_index][k] = v\n",
    "                count[nxt_index][weight] += 1\n",
    "                dfs(nxt_index, cur_depth + 1, cur_index)\n",
    "\n",
    "        dfs(0, 0, -1)\n",
    "        ancestor = [[-1] * n.bit_length() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ancestor[i][0] = parent[i]\n",
    "        for j in range(1, n.bit_length()):\n",
    "            for i in range(n):\n",
    "                if ancestor[i][j - 1] != -1:\n",
    "                    ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1]\n",
    "\n",
    "        def get_ancestor(node: int, k: int):\n",
    "            for kk in range(k.bit_length()):\n",
    "                if (1 << kk) & k:\n",
    "                    node = ancestor[node][kk]\n",
    "            return node\n",
    "\n",
    "        ans = []\n",
    "        for x, y in queries:\n",
    "            count_x = count[x]\n",
    "            count_y = count[y]\n",
    "            dx = depth[x]\n",
    "            dy = depth[y]\n",
    "            if dx < dy:\n",
    "                y = get_ancestor(y, dy - dx)\n",
    "            else:\n",
    "                x = get_ancestor(x, dx - dy)\n",
    "            flag = (x != y)\n",
    "            while flag:\n",
    "                for i in range(n.bit_length()):\n",
    "                    px = ancestor[x][i]\n",
    "                    py = ancestor[y][i]\n",
    "                    if px == py:\n",
    "                        if i == 0:\n",
    "                            x = px\n",
    "                            flag = False\n",
    "                        else:\n",
    "                            x = ancestor[x][i - 1]\n",
    "                            y = ancestor[y][i - 1]\n",
    "                        break\n",
    "            count_xy = count[x]\n",
    "            lst = [0] * 27\n",
    "            for k, v in count_x.items():\n",
    "                lst[k] += v\n",
    "            for k, v in count_y.items():\n",
    "                lst[k] += v\n",
    "            for k, v in count_xy.items():\n",
    "                lst[k] -= 2 * v\n",
    "            ans.append(sum(lst) - max(lst))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5\n",
    "lg = [0] * (N + 1)\n",
    "lg[1] = 0\n",
    "for i in range(2, N + 1):\n",
    "    lg[i] = lg[i // 2] + 1\n",
    "L = 20\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(Counter)\n",
    "        G = [[] for _ in range(n + 1)]\n",
    "        for a, b, w in edges:\n",
    "            G[a + 1].append((b + 1, w))\n",
    "            G[b + 1].append((a + 1, w))\n",
    "        \n",
    "        def dfs(i, pre, par):\n",
    "            for j, w in G[i]:\n",
    "                if j == par: continue\n",
    "                tmp = copy.deepcopy(pre)\n",
    "                tmp[w] += 1\n",
    "                dic[j] = tmp\n",
    "                dfs(j, tmp, i)\n",
    "                \n",
    "        dfs(1, Counter(), 0)\n",
    "        \n",
    "        f = defaultdict(lambda: defaultdict(int))\n",
    "        dep = [0] * (n + 2)\n",
    "        def dfs2(i, par):\n",
    "            f[i][0] = par\n",
    "            if i == 1:\n",
    "                dep[i] = 0\n",
    "            else:\n",
    "                dep[i] = dep[par] + 1\n",
    "            for j, _ in G[i]:\n",
    "                if j == par: continue\n",
    "                dfs2(j, i)\n",
    "        \n",
    "        dfs2(1, 0)\n",
    "        # print(dep, f)\n",
    "        \n",
    "        \n",
    "        \n",
    "        def lca(x, y):\n",
    "            if dep[x] < dep[y]:\n",
    "                x, y = y, x\n",
    "            i = 0\n",
    "            while dep[x] != dep[y]:\n",
    "                z = dep[x] - dep[y]\n",
    "                x = f[x][lg[z]]\n",
    "            if x == y: return y\n",
    "            for i in range(L - 1, -1, -1):\n",
    "                if f[x][i] != f[y][i]:\n",
    "                    x = f[x][i]\n",
    "                    y = f[y][i]\n",
    "            return f[y][0]\n",
    "        \n",
    "        \n",
    "        for j in range(1, L):\n",
    "            for i in range(1, n + 1):\n",
    "                f[i][j] = f[f[i][j - 1]][j - 1]\n",
    "        # print(f)\n",
    "        # print(dic)\n",
    "        \n",
    "        \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            a += 1\n",
    "            b += 1\n",
    "            c = lca(a, b)\n",
    "            x = dic[a] - dic[c]\n",
    "            y = dic[b] - dic[c]\n",
    "            s1 = sum(x.values())\n",
    "            s2 = sum(y.values())\n",
    "            tmp = inf\n",
    "            for p in range(1, 27):\n",
    "                p1 = x[p]\n",
    "                p2 = y[p]\n",
    "                tmp = min(tmp, s1 + s2 - p1 - p2)\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "'''\n",
    "问题简化后可以分为两个子问题：\n",
    "1. 找到uv两点间的链路并找出链路上权重出现最多的数字的次数，那么除此之外的边权都需要改；\n",
    "2. uv的链路 = (u到根0经过的边 - LCA到根0的边) + (v到根0经过的边 - LCA到根0的边)；\n",
    "\n",
    "由于边权只有26种可能，所以直接建表排查即可，不会是瓶颈，所以 找LCA 才是解题关键；\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        # 建图并以0节点为根建树、建立父链、标记节点距离0节点的深度值\n",
    "        graph, depth, parent = [[] for _ in range(n)], [0] * n, [0] * n\n",
    "        maxW = 0\n",
    "        for u,v,w in edges:\n",
    "            fw = w - 1\n",
    "            graph[u].append([v,fw])\n",
    "            graph[v].append([u,fw])\n",
    "            if maxW < w: maxW = w\n",
    "        \n",
    "        dps = [None] * n\n",
    "        dps[0] = [0] * maxW\n",
    "\n",
    "        def dfs(pre: int, cur: int, w: int, d: int):\n",
    "            dps[cur] = [i for i in dps[pre]]\n",
    "            dps[cur][w] += 1\n",
    "            depth[cur] = d\n",
    "            parent[cur] = pre\n",
    "            for nexV, nexW in graph[cur]:\n",
    "                if nexV == pre: continue\n",
    "                dfs(cur, nexV, nexW, d + 1)\n",
    "            \n",
    "        for v,w in graph[0]:\n",
    "            dfs(0, v, w, 1)\n",
    "       \n",
    "        # 倍增入口，返回当前节点root向0根方向跳2^powStep下应该是那个节点\n",
    "        @cache\n",
    "        def powJumpTo(root: int, powStep: int) -> int:\n",
    "            if powStep == 0: return parent[root]\n",
    "            return powJumpTo(powJumpTo(root, powStep - 1), powStep - 1)\n",
    "        \n",
    "        # 深度跳转入口，返回当前节点root向0根方向上升到目标深度targetDepth时是哪个节点\n",
    "        @cache\n",
    "        def jumpTo(root: int, targetDepth: int) -> int:\n",
    "            rootDepth = depth[root]\n",
    "            if rootDepth == targetDepth: return root\n",
    "            num, step = rootDepth - targetDepth, 0\n",
    "            while num:\n",
    "                if num & 1 == 1: root = powJumpTo(root, step)\n",
    "                num >>= 1\n",
    "                step += 1\n",
    "            return root\n",
    "\n",
    "        # 答案具体搜索入口，先调整u深度到v一致的位置，如果重合直接输出答案，如果不是，倍增找LCA\n",
    "        @cache\n",
    "        def checkFn(u: int, v: int) -> int:\n",
    "            nu, nv, p = jumpTo(u, depth[v]), v, -1\n",
    "            curDepth = depth[v]\n",
    "\n",
    "            # 枚举最近公共祖先 - 超时\n",
    "            # while jumpTo(nu, curDepth) != jumpTo(nv, curDepth): curDepth -= 1\n",
    "            \n",
    "            # 根据深度二分搜索最近公共祖先 2550ms\n",
    "            # if nu == nv: p = nu\n",
    "            # else:\n",
    "            #     left, right = 0, curDepth\n",
    "            #     while left <= right:\n",
    "            #         mid = (left + right) >> 1\n",
    "            #         if jumpTo(nu, mid) == jumpTo(nv, mid): left =  mid + 1\n",
    "            #         else: right = mid - 1\n",
    "            #     p = jumpTo(nu, right)\n",
    "\n",
    "            # 二分倍数搜索最近公共祖先 2500ms\n",
    "            if nu == nv: p = nu\n",
    "            else:\n",
    "                step = ceil(log2(curDepth)) \n",
    "                while step >= 0:\n",
    "                    if powJumpTo(nu,step) == powJumpTo(nv,step): step -= 1\n",
    "                    else: nu, nv = powJumpTo(nu,step), powJumpTo(nv,step)\n",
    "                p = parent[nu]\n",
    "\n",
    "            maxNum, total = 0, 0\n",
    "            for i in range(maxW):\n",
    "                num = dps[u][i] + dps[v][i] - dps[p][i] * 2\n",
    "                if maxNum < num: maxNum = num\n",
    "                total += num\n",
    "            return total - maxNum\n",
    "\n",
    "        # 答案入口，统一深度u比v大\n",
    "        def check(u: int, v: int) -> int:\n",
    "            if depth[u] < depth[v]: u,v = v,u\n",
    "            return checkFn(u,v)\n",
    "\n",
    "        return [check(u, v) for u,v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "'''\n",
    "问题简化后可以分为两个子问题：\n",
    "1. 找到uv两点间的链路并找出链路上权重出现最多的数字的次数，那么除此之外的边权都需要改；\n",
    "2. uv的链路 = (u到根0经过的边 - LCA到根0的边) + (v到根0经过的边 - LCA到根0的边)；\n",
    "\n",
    "由于边权只有26种可能，所以直接建表排查即可，不会是瓶颈，所以 找LCA 才是解题关键；\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        # 建图并以0节点为根建树、建立父链、标记节点距离0节点的深度值\n",
    "        graph, depth, parent = [[] for _ in range(n)], [0] * n, [0] * n\n",
    "        maxW = 0\n",
    "        for u,v,w in edges:\n",
    "            fw = w - 1\n",
    "            graph[u].append([v,fw])\n",
    "            graph[v].append([u,fw])\n",
    "            if maxW < w: maxW = w\n",
    "        \n",
    "        dps = [None] * n\n",
    "        dps[0] = [0] * maxW\n",
    "\n",
    "        def dfs(pre: int, cur: int, w: int, d: int):\n",
    "            dps[cur] = [i for i in dps[pre]]\n",
    "            dps[cur][w] += 1\n",
    "            depth[cur] = d\n",
    "            parent[cur] = pre\n",
    "            for nexV, nexW in graph[cur]:\n",
    "                if nexV == pre: continue\n",
    "                dfs(cur, nexV, nexW, d + 1)\n",
    "            \n",
    "        for v,w in graph[0]:\n",
    "            dfs(0, v, w, 1)\n",
    "       \n",
    "        # 倍增入口，返回当前节点root向0根方向跳2^powStep下应该是那个节点\n",
    "        @cache\n",
    "        def powJumpTo(root: int, powStep: int) -> int:\n",
    "            if powStep == 0: return parent[root]\n",
    "            return powJumpTo(powJumpTo(root, powStep - 1), powStep - 1)\n",
    "        \n",
    "        # 深度跳转入口，返回当前节点root向0根方向上升到目标深度targetDepth时是哪个节点\n",
    "        @cache\n",
    "        def jumpTo(root: int, targetDepth: int) -> int:\n",
    "            rootDepth = depth[root]\n",
    "            if rootDepth == targetDepth: return root\n",
    "            num, step = rootDepth - targetDepth, 0\n",
    "            while num:\n",
    "                if num & 1 == 1: root = powJumpTo(root, step)\n",
    "                num >>= 1\n",
    "                step += 1\n",
    "            return root\n",
    "\n",
    "        # 答案具体搜索入口，先调整u深度到v一致的位置，如果重合直接输出答案，如果不是，倍增找LCA\n",
    "        @cache\n",
    "        def checkFn(u: int, v: int) -> int:\n",
    "            nu, nv, lca = jumpTo(u, depth[v]), v, -1\n",
    "            curDepth = depth[v]\n",
    "\n",
    "            # 枚举最近公共祖先 - 超时\n",
    "            # while jumpTo(nu, curDepth) != jumpTo(nv, curDepth): curDepth -= 1\n",
    "            # lca = jumpTo(nu, curDepth)\n",
    "            \n",
    "            # 根据深度二分搜索最近公共祖先 2550ms\n",
    "            # if nu == nv: lca = nu\n",
    "            # else:\n",
    "            #     left, right = 0, curDepth\n",
    "            #     while left <= right:\n",
    "            #         mid = (left + right) >> 1\n",
    "            #         if jumpTo(nu, mid) == jumpTo(nv, mid): left =  mid + 1\n",
    "            #         else: right = mid - 1\n",
    "            #     lca = jumpTo(nu, right)\n",
    "\n",
    "            # 二分倍数搜索最近公共祖先 2500ms\n",
    "            if nu == nv: lca = nu\n",
    "            else:\n",
    "                step = ceil(log2(curDepth)) \n",
    "                while step >= 0:\n",
    "                    if powJumpTo(nu,step) == powJumpTo(nv,step): step -= 1\n",
    "                    else: nu, nv = powJumpTo(nu,step), powJumpTo(nv,step)\n",
    "                lca = parent[nu]\n",
    "\n",
    "\n",
    "            maxNum, total = 0, 0\n",
    "            for i in range(maxW):\n",
    "                num = dps[u][i] + dps[v][i] - dps[lca][i] * 2\n",
    "                if maxNum < num: maxNum = num\n",
    "                total += num\n",
    "            return total - maxNum\n",
    "\n",
    "        # 答案入口，统一深度u比v大\n",
    "        def check(u: int, v: int) -> int:\n",
    "            if depth[u] < depth[v]: u,v = v,u\n",
    "            return checkFn(u,v)\n",
    "\n",
    "        return [check(u, v) for u,v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        \n",
    "        f = [Counter() for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "        \n",
    "        MAXF = 16\n",
    "        father = [[0] * MAXF for _ in range(n)]\n",
    "        \n",
    "        def update(u, v, w):\n",
    "            for x, cnt in f[u].items():\n",
    "                f[v][x] = cnt\n",
    "            f[v][w] += 1\n",
    "        \n",
    "        def dfs(p, u):\n",
    "            if p >= 0:\n",
    "                father[u][0] = p;\n",
    "                for i in range(1, MAXF):\n",
    "                    father[u][i] = father[father[u][i-1]][i-1];\n",
    "                    \n",
    "            for v, w in g[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                \n",
    "                update(u, v, w)\n",
    "                depth[v] = depth[u] + 1\n",
    "                \n",
    "                dfs(u, v)\n",
    "        \n",
    "        dfs(-1, 0)\n",
    "        #print(depth)\n",
    "        #print(father)\n",
    "        \n",
    "        def lca(a, b):\n",
    "            #print(a, b)\n",
    "            while depth[a] < depth[b]:\n",
    "                for i in range(MAXF-1, -1, -1):\n",
    "                    if depth[b] - (1 << i) >= depth[a]:\n",
    "                        b = father[b][i]\n",
    "            \n",
    "            while depth[a] > depth[b]:\n",
    "                for i in range(MAXF-1, -1, -1):\n",
    "                    if depth[a] - (1 << i) >= depth[b]:\n",
    "                        a = father[a][i]\n",
    "            \n",
    "            if a == b:\n",
    "                return a\n",
    "            \n",
    "            while father[a][0] != father[b][0]:\n",
    "                for i in range(MAXF-1, -1, -1):\n",
    "                    if father[a][i] != father[b][i]:\n",
    "                        a = father[a][i]\n",
    "                        b = father[b][i]\n",
    "            \n",
    "            return father[a][0]\n",
    "        \n",
    "        def solve(a, b, p):\n",
    "            mx = 0\n",
    "            t = 0\n",
    "            for i in range(1, 27):\n",
    "                c1 = (f[a][i] - f[p][i])\n",
    "                c2 = (f[b][i] - f[p][i])\n",
    "                mx = max(mx, c1 + c2)\n",
    "                t += c1 + c2\n",
    "            \n",
    "            return t - mx\n",
    "        \n",
    "        nq = len(queries)\n",
    "        res = [0] * nq\n",
    "        for i in range(nq):\n",
    "            a, b = queries[i]\n",
    "            p = lca(a, b)\n",
    "            \n",
    "            res[i] = solve(a, b, p)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        \n",
    "        f = [Counter() for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "        \n",
    "        MAXF = 30\n",
    "        father = [[0] * MAXF for _ in range(n)]\n",
    "        \n",
    "        def update(u, v, w):\n",
    "            for x, cnt in f[u].items():\n",
    "                f[v][x] = cnt\n",
    "            f[v][w] += 1\n",
    "        \n",
    "        def dfs(p, u):\n",
    "            if p >= 0:\n",
    "                father[u][0] = p;\n",
    "                for i in range(1, MAXF):\n",
    "                    father[u][i] = father[father[u][i-1]][i-1];\n",
    "                    \n",
    "            for v, w in g[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                \n",
    "                update(u, v, w)\n",
    "                depth[v] = depth[u] + 1\n",
    "                \n",
    "                dfs(u, v)\n",
    "        \n",
    "        dfs(-1, 0)\n",
    "        #print(depth)\n",
    "        #print(father)\n",
    "        \n",
    "        def lca(a, b):\n",
    "            #print(a, b)\n",
    "            while depth[a] < depth[b]:\n",
    "                for i in range(MAXF-1, -1, -1):\n",
    "                    if depth[b] - (1 << i) >= depth[a]:\n",
    "                        b = father[b][i]\n",
    "            \n",
    "            while depth[a] > depth[b]:\n",
    "                for i in range(MAXF-1, -1, -1):\n",
    "                    if depth[a] - (1 << i) >= depth[b]:\n",
    "                        a = father[a][i]\n",
    "            \n",
    "            if a == b:\n",
    "                return a\n",
    "            \n",
    "            while father[a][0] != father[b][0]:\n",
    "                for i in range(MAXF-1, -1, -1):\n",
    "                    if father[a][i] != father[b][i]:\n",
    "                        a = father[a][i]\n",
    "                        b = father[b][i]\n",
    "            \n",
    "            return father[a][0]\n",
    "        \n",
    "        def solve(a, b, p):\n",
    "            mx = 0\n",
    "            t = 0\n",
    "            for i in range(1, 27):\n",
    "                c1 = (f[a][i] - f[p][i])\n",
    "                c2 = (f[b][i] - f[p][i])\n",
    "                mx = max(mx, c1 + c2)\n",
    "                t += c1 + c2\n",
    "            \n",
    "            return t - mx\n",
    "        \n",
    "        nq = len(queries)\n",
    "        res = [0] * nq\n",
    "        for i in range(nq):\n",
    "            a, b = queries[i]\n",
    "            p = lca(a, b)\n",
    "            \n",
    "            res[i] = solve(a, b, p)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjointSet:\n",
    "    \"\"\"并查集\n",
    "    Attributes:\n",
    "        1. size：元素数\n",
    "    Application:\n",
    "        1. 无向图连通性判定\n",
    "        2. 无向图中判定是否存在环\n",
    "    \"\"\"\n",
    "\n",
    "    @property\n",
    "    def size(self):\n",
    "        return self._n\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self._heads = [i for i in range(n)]\n",
    "        self._cnts = [1] * n\n",
    "\n",
    "    def find(self, t):\n",
    "        \"\"\"\n",
    "        Returns:\n",
    "            元素t所在group的头结点\n",
    "        Attention:\n",
    "            查找过程中会进行路径压缩，修改head列表\n",
    "        Time Complexity:\n",
    "            O(1)\n",
    "        \"\"\"\n",
    "        if self._heads[t] != t:\n",
    "            self._heads[t] = self.find(self._heads[t])\n",
    "        return self._heads[t]\n",
    "\n",
    "    def union(self, p, q, opt=True):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            opt：是否执行优化：将节点数少的子树合并到节点数多的子树\n",
    "        Attention：\n",
    "            若opt设为False，则将q所在子树合并到p所在子树\n",
    "        Returns:\n",
    "            是否实际执行合并操作\n",
    "        Time Complexity:\n",
    "            O(1)\n",
    "        \"\"\"\n",
    "        hp = self.find(p)\n",
    "        hq = self.find(q)\n",
    "        if hp == hq:\n",
    "            return False\n",
    "        if opt and self._cnts[hp] < self._cnts[hq]:\n",
    "            hp, hq = hq, hp\n",
    "        self._heads[hq] = hp\n",
    "        self._cnts[hp] += self._cnts[hq]\n",
    "        self._cnts[hq] = 0\n",
    "        return True\n",
    "\n",
    "    def getGroupCount(self, t):\n",
    "        \"\"\"\n",
    "        Returns:\n",
    "            元素t所在group的元素数\n",
    "        Time Complexity:\n",
    "            O(1)\n",
    "        \"\"\"\n",
    "        return self._cnts[self.find(t)]\n",
    "    \n",
    "def lca(edges, root, querys):\n",
    "    \"\"\"最近公共祖先的tarjan离线算法\n",
    "    Returns:\n",
    "        针对每个query的最近公共祖先列表\n",
    "    Args:\n",
    "        edges：树的边列表。每个节点必须为0 ~ len(edges)。如：[(0, 1), (0, 2), (3, 2)]\n",
    "        root：树的根节点\n",
    "        querys：LCA询问列表。如：[(0, 1), (1, 3)]\n",
    "    Time Complexity:\n",
    "        O(n + m)\n",
    "    \"\"\"\n",
    "    n = len(edges) + 1\n",
    "    m = len(querys)\n",
    "    e = [[] for _ in range(n)]\n",
    "    for i, (u, v) in enumerate(edges):\n",
    "        e[u].append(v)\n",
    "        e[v].append(u)\n",
    "    q = [[] for _ in range(n)]\n",
    "    for i, (u, v) in enumerate(querys):\n",
    "        q[u].append((v, i))\n",
    "        q[v].append((u, i))\n",
    "\n",
    "    ans = [0] * m\n",
    "    vis = [False] * n\n",
    "    ds = DisjointSet(n)\n",
    "\n",
    "    def tarjan(k):\n",
    "        vis[k] = True\n",
    "        for t in e[k]:\n",
    "            if vis[t]:\n",
    "                continue\n",
    "            tarjan(t)\n",
    "            ds.union(k, t, False)\n",
    "        for t, id in q[k]:\n",
    "            if vis[t]:\n",
    "                ans[id] = ds.find(t)\n",
    "\n",
    "    tarjan(root)\n",
    "\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges, queries):\n",
    "        e = [[] for _ in range(n)]\n",
    "        for p, q, w in edges:\n",
    "            e[p].append((q, w))\n",
    "            e[q].append((p, w))\n",
    "        s = [[0] * 27 for _ in range(n)]\n",
    "        \n",
    "        def dfs(t, last, l):\n",
    "            for q, w in e[t]:\n",
    "                if q == last:\n",
    "                    continue\n",
    "                for i in range(1, 27):\n",
    "                    s[q][i] = s[t][i] + (w != i)\n",
    "                dfs(q, t, l + 1)\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "        \n",
    "        ans = []\n",
    "        a = lca([(u, v) for (u, v, w) in edges], 0, queries)\n",
    "        for k, (u, v) in enumerate(queries):\n",
    "            t = min([s[u][i] + s[v][i] - 2 * s[a[k]][i] for i in range(1, 27)])\n",
    "            ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        def find_cm(u, v):\n",
    "            if node_depth[u] > node_depth[v]:\n",
    "                u, v = v, u\n",
    "            diff = node_depth[v] - node_depth[u]\n",
    "            for i in range(32):\n",
    "                if diff >> i & 1:\n",
    "                    v = parent_fa[v][i]\n",
    "            assert node_depth[v] == node_depth[u]\n",
    "\n",
    "            for i in range(31, -1, -1):\n",
    "                if parent_fa[u][i] != parent_fa[v][i]:\n",
    "                    u = parent_fa[u][i]\n",
    "                    v = parent_fa[v][i]\n",
    "            \n",
    "            while u != v:\n",
    "                u = parent_fa[u][0]\n",
    "                v = parent_fa[v][0]\n",
    "            \n",
    "            return u\n",
    "    \n",
    "        \n",
    "        neb = defaultdict(dict)\n",
    "        for u, v, w in edges:\n",
    "            neb[u][v] = w\n",
    "            neb[v][u] = w\n",
    "            \n",
    "        Log2 = [0] * (n+1)\n",
    "        for i in range(2, n+1):\n",
    "            Log2[i] = Log2[i // 2] + 1;\n",
    "            \n",
    "    \n",
    "        pp_fa = list()\n",
    "        node_depth = [-1] * n\n",
    "        parent_fa = list([None] * 32 for _ in range(n))\n",
    "        def dfs(u, fa, ow, depth):\n",
    "            node_cnt[u][ow] += 1\n",
    "            node_depth[u] = depth\n",
    "            parent_fa[u][0] = fa\n",
    "            for i in range(1, 32):\n",
    "                if 2**i <= depth:\n",
    "                    parent_fa[u][i] = parent_fa[parent_fa[u][i-1]][i-1]\n",
    "\n",
    "            for _w, _cnt in node_cnt[fa].items():\n",
    "                node_cnt[u][_w] += _cnt\n",
    "            for v, w in neb[u].items():\n",
    "                if v != fa:\n",
    "                    dfs(v, u, w, depth+1)\n",
    "        \n",
    "        node_cnt = [Counter() for _ in range(n)]\n",
    "        dfs(0, -1, -1, 0)\n",
    "        #print(node_cnt)\n",
    "        \n",
    "        res = []\n",
    "        for u, v in queries:\n",
    "            cc = find_cm(u, v)\n",
    "            remain = node_cnt[u] + node_cnt[v] - node_cnt[cc] - node_cnt[cc]\n",
    "            if remain:\n",
    "                v = remain.most_common(1)[0][1]\n",
    "                res.append(sum(remain.values()) - v)\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        e = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            e[u].append((v, w))\n",
    "            e[v].append((u, w))\n",
    "\n",
    "        depth = [0] * n\n",
    "        f = [[0] * 31 for _ in range(n)]\n",
    "        cnt = defaultdict(Counter)\n",
    "        def dfs(u: int, p: int, w: int):\n",
    "            if p != -1:\n",
    "                depth[u] = depth[p] + 1\n",
    "                f[u][0] = p\n",
    "                for i in range(1, 27):\n",
    "                    cnt[u][i] += cnt[p][i]\n",
    "                cnt[u][w] += 1\n",
    "            for i in range(1, 31):\n",
    "                f[u][i] = f[f[u][i - 1]][i - 1]\n",
    "            for v, w in e[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                dfs(v, u, w)\n",
    "        dfs(0, -1, 0)\n",
    "\n",
    "        def lca(x: int, y: int) -> int:\n",
    "            if depth[x] > depth[y]:\n",
    "                x, y = y, x\n",
    "            temp = depth[y] - depth[x]\n",
    "            i = 0\n",
    "            while temp:\n",
    "                if temp & 1:\n",
    "                    y = f[y][i]\n",
    "                i += 1\n",
    "                temp >>= 1\n",
    "            if x == y:\n",
    "                return y\n",
    "            for j in range(30, -1, -1):\n",
    "                if y == x:\n",
    "                    break\n",
    "                if f[x][j] != f[y][j]:\n",
    "                    x = f[x][j]\n",
    "                    y = f[y][j]\n",
    "            return y if y == x else f[y][0]\n",
    "        \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            c = lca(a, b)\n",
    "            vis1, vis2 = [0] * 26, [0] * 26\n",
    "            for i in range(1, 27):\n",
    "                vis1[i - 1] = cnt[a][i] - cnt[c][i]\n",
    "                vis2[i - 1] = cnt[b][i] - cnt[c][i]\n",
    "            mx = tot = 0\n",
    "            for i in range(26):\n",
    "                mx = max(mx, vis1[i] + vis2[i])\n",
    "                tot += vis1[i] + vis2[i]\n",
    "            ans.append(tot - mx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        cnt=[[0]*27 for i in range(n)]\n",
    "        d=defaultdict()\n",
    "        g=[[] for i in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append([y,w])\n",
    "            g[y].append([x,w])\n",
    "        def dfs(x,pa):\n",
    "            for y,w in g[x]:\n",
    "                if y!=pa:\n",
    "                    cnt[y]=cnt[x][:]\n",
    "                    cnt[y][0]=cnt[x][0]|1<<y\n",
    "                    d[cnt[y][0]]=y\n",
    "                    cnt[y][w]+=1\n",
    "                    dfs(y,x)\n",
    "        d[0]=0\n",
    "        dfs(0,-1)\n",
    "        res=[]\n",
    "\n",
    "        for qx,qy in queries:\n",
    "            tmp=[0]*27\n",
    "            s=0\n",
    "            if cnt[qx][0]&cnt[qy][0]==0:\n",
    "                for i in range(1,27):\n",
    "                    tmp[i]=cnt[qx][i]+cnt[qy][i]\n",
    "                    s+=tmp[i]\n",
    "                res.append(s-max(tmp))\n",
    "            else:\n",
    "                a=cnt[qx][0]&cnt[qy][0]\n",
    "\n",
    "                for i in range(1,27):\n",
    "                    tmp[i]=cnt[qx][i]+cnt[qy][i]-2*cnt[d[a]][i]\n",
    "                    s+=tmp[i]\n",
    "\n",
    "                res.append(s-max(tmp))\n",
    "                \n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w-1))\n",
    "            g[y].append((x,w-1))\n",
    "\n",
    "        deep = [0] * n\n",
    "        pa = [(-1,-1)] * n\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            for y,w in g[x]:\n",
    "                if(y == fa): continue\n",
    "                nonlocal deep\n",
    "                deep[y] = deep[x] + 1\n",
    "                pa[y] = (x,w)\n",
    "                dfs(y, x)\n",
    "        dfs(0,-1)\n",
    "\n",
    "        m = n.bit_length() - 1\n",
    "        f = [[p] + [-1]*m for p,w in pa]\n",
    "        cnt = [[[0] * 26 for _ in range(m+1)] for p,w in pa]\n",
    "        for i,(p,w) in enumerate(pa):\n",
    "            cnt[i][0][w] = 1\n",
    "\n",
    "        for j in range(m):\n",
    "            for i in range(n):\n",
    "                s = f[i][j]\n",
    "                if s != -1:\n",
    "                    f[i][j+1] = f[s][j]\n",
    "\n",
    "                    for k in range(26):\n",
    "                        cnt[i][j+1][k] = cnt[i][j][k] + cnt[s][j][k]\n",
    "\n",
    "        def jump(i: int, k: int) -> int:\n",
    "            x = i\n",
    "            nonlocal cw\n",
    "            for j in range(m+1):\n",
    "                if(k >> j & 1):\n",
    "                    for q in range(26):\n",
    "                        cw[q] += cnt[x][j][q]\n",
    "                    x = f[x][j]\n",
    "\n",
    "            return x\n",
    "\n",
    "\n",
    "        # print(deep)\n",
    "        # print(f)\n",
    "\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if(deep[a] > deep[b]):\n",
    "                a,b = b,a\n",
    "            tmp = deep[a] + deep[b]\n",
    "            cw = [0] * 26\n",
    "            b = jump(b, deep[b] - deep[a])\n",
    "            # a.b 位于同一层\n",
    "\n",
    "            # print(a, b)\n",
    "\n",
    "            if(a != b):\n",
    "                for j in range(m,-1,-1):\n",
    "                    if(f[a][j] != f[b][j]):\n",
    "                        for q in range(26):\n",
    "                            cw[q] += cnt[a][j][q] + cnt[b][j][q]\n",
    "                        a, b = f[a][j], f[b][j]\n",
    "\n",
    "                for q in range(26):\n",
    "                    cw[q] += cnt[a][0][q] + cnt[b][0][q]\n",
    "                lca = f[a][0]\n",
    "            else:\n",
    "                lca = a\n",
    "\n",
    "            # print(lca)\n",
    "\n",
    "            ans.append(tmp - 2*deep[lca] - max(cw))\n",
    "\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges, queries):\n",
    "        e = [[] for _ in range(n)]\n",
    "        for p, q, w in edges:\n",
    "            e[p].append((q, w))\n",
    "            e[q].append((p, w))\n",
    "        m = n.bit_length() + 1\n",
    "        p = [[-1] * m for _ in range(n)]\n",
    "        h = [0] * n\n",
    "        s = [[0] * 27 for _ in range(n)]\n",
    "        \n",
    "        def dfs(t, last, l):\n",
    "            h[t] = l\n",
    "            for q, w in e[t]:\n",
    "                if q == last:\n",
    "                    continue\n",
    "                p[q][0] = t\n",
    "                for i in range(1, m):\n",
    "                    p[q][i] = p[p[q][i - 1]][i - 1]\n",
    "                    if p[q][i] == -1:\n",
    "                        break\n",
    "                for i in range(1, 27):\n",
    "                    s[q][i] = s[t][i] + (w != i)\n",
    "                dfs(q, t, l + 1)\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "        \n",
    "        @functools.cache\n",
    "        def get(u, v):\n",
    "            if h[u] < h[v]:\n",
    "                return get(v, u)\n",
    "            if u == v:\n",
    "                return u\n",
    "            if h[u] == h[v]:\n",
    "                for i in range(1, m):\n",
    "                    if p[u][i] == p[v][i]:\n",
    "                        return get(p[u][i - 1], p[v][i - 1])\n",
    "            for i in range(m):\n",
    "                if p[u][i] == -1 or h[p[u][i]] < h[v]:\n",
    "                    return get(v, p[u][i - 1])\n",
    "        \n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            a = get(u, v)\n",
    "            t = min([s[u][i] + s[v][i] - 2 * s[a][i] for i in range(1, 27)])\n",
    "            ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        d = defaultdict(list)\n",
    "        for a,b,w in edges:\n",
    "            d[a].append((b,chr(ord('a')+w-1)))\n",
    "            d[b].append((a,chr(ord('a')+w-1)))\n",
    "        fa = [[] for _ in range(n+1)]\n",
    "        fa[-1].append(-1)\n",
    "        fa[0].append(-1)\n",
    "        route = [''] * n\n",
    "        depth = [0]*n\n",
    "\n",
    "        queue = [0]\n",
    "        while queue:\n",
    "            anc = queue.pop(0)\n",
    "            for child, c in d[anc]:\n",
    "                if child!=0 and depth[child]==0:\n",
    "                    fa[child].append(anc)\n",
    "                    route[child] = route[anc]+c\n",
    "                    depth[child] = depth[anc]+1\n",
    "                    queue.append(child)\n",
    "        max_depth = max(depth)\n",
    "        cur_depth = 1\n",
    "        while 2**cur_depth<=max_depth:\n",
    "            for i in range(n):\n",
    "                fa[i].append(fa[fa[i][cur_depth-1]][cur_depth-1])\n",
    "            fa[-1].append(-1)\n",
    "            cur_depth+=1\n",
    "        \n",
    "        # print(d)\n",
    "        # print(route)\n",
    "        # print(depth)\n",
    "        # print(fa)\n",
    "        def upward(node, step):\n",
    "            # print('upward', node,step)\n",
    "            if step==0:\n",
    "                return node\n",
    "            b = bin(step)[2:]\n",
    "\n",
    "            for i in range(len(b)):\n",
    "                if b[i]=='1':\n",
    "                    node = fa[node][len(b)-i-1]\n",
    "            # print('upwardend', node)\n",
    "            return node\n",
    "\n",
    "        def get_lca(a,b):\n",
    "            if a==0 or b==0:\n",
    "                return 0\n",
    "            lcpdepth = len(os.path.commonprefix([route[a], route[b]]))\n",
    "            if lcpdepth==0:\n",
    "                return 0\n",
    "            a = upward(a, depth[a]-lcpdepth)\n",
    "            b = upward(b, depth[b]-lcpdepth)\n",
    "            if a==b:\n",
    "                return a\n",
    "            step = int(math.log(lcpdepth,2))\n",
    "            while a!=b and step>=0:\n",
    "                # print(a,b,step)\n",
    "                if fa[a][step]!=fa[b][step]:\n",
    "                    a,b=fa[a][step], fa[b][step]\n",
    "                step-=1\n",
    "            return fa[a][0]\n",
    "        \n",
    "        ans = []\n",
    "        for a,b in queries:\n",
    "            if a==b:\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            lca = get_lca(a,b)\n",
    "            l = depth[lca]\n",
    "            d = Counter(route[a][l:]+route[b][l:])\n",
    "            # print(depth, a, b, l, d)\n",
    "            ans.append(depth[a]+depth[b]-2*l-max(d.values()))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append((v, w))\n",
    "            graph[v].append((u, w))\n",
    "\n",
    "        parent = [-1] * n\n",
    "        dist = [[0] * 27 for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "        stack = [(0, -1, 0)]\n",
    "\n",
    "        while stack:\n",
    "            node, par, d = stack.pop()\n",
    "            parent[node] = par\n",
    "            depth[node] = d\n",
    "            for neighbor, weight in graph[node]:\n",
    "                if neighbor != par:\n",
    "                    dist[neighbor][weight] += 1\n",
    "                    stack.append((neighbor, node, d + 1))\n",
    "\n",
    "        max_log = int(log2(n)) + 1\n",
    "        parent_ancestors = [[-1] * max_log for _ in range(n)]\n",
    "        #dist_ancestors = [[0] * max_log for _ in range(n)]\n",
    "        dist_ancestors = [[[0 for _ in range(27)] for _ in range(max_log)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            parent_ancestors[i][0] = parent[i]\n",
    "            dist_ancestors[i][0] = dist[i]\n",
    "\n",
    "        for j in range(1, max_log):\n",
    "            for i in range(n):\n",
    "                if parent_ancestors[i][j - 1] != -1:\n",
    "                    parent_ancestors[i][j] = parent_ancestors[parent_ancestors[i][j - 1]][j - 1]\n",
    "                    for k in range(27):\n",
    "                        dist_ancestors[i][j][k] = dist_ancestors[i][j - 1][k] + dist_ancestors[parent_ancestors[i][j - 1]][j - 1][k]\n",
    "\n",
    "        def query(a, b):\n",
    "            if depth[a] < depth[b]:\n",
    "                a, b = b, a\n",
    "\n",
    "            result = [0] * 27\n",
    "            diff = depth[a] - depth[b]\n",
    "\n",
    "            for i in range(max_log):\n",
    "                if diff & (1 << i):\n",
    "                    for k in range(27):\n",
    "                        result[k] += dist_ancestors[a][i][k]\n",
    "                    a = parent_ancestors[a][i]\n",
    "\n",
    "            if a == b:\n",
    "                return sum(result) - max(result)\n",
    "\n",
    "            for i in range(max_log - 1, -1, -1):\n",
    "                if parent_ancestors[a][i] != parent_ancestors[b][i]:\n",
    "                    for k in range(27):\n",
    "                        result[k] += dist_ancestors[a][i][k] + dist_ancestors[b][i][k]\n",
    "                    a = parent_ancestors[a][i]\n",
    "                    b = parent_ancestors[b][i]\n",
    "            for k in range(27):\n",
    "                result[k] += dist[a][k] + dist[b][k]\n",
    "            return sum(result) - max(result)\n",
    "\n",
    "        ans = [query(a, b) for a, b in queries]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x].append((y, w - 1))\n",
    "            g[y].append((x, w - 1))\n",
    "\n",
    "        m = n.bit_length()\n",
    "        pa = [[-1] * m for _ in range(n)]\n",
    "        cnt = [[[0] * 26 for _ in range(m)] for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "\n",
    "        def dfs(x, p):\n",
    "            pa[x][0] = p\n",
    "            for y, w in g[x]:\n",
    "                if y != p:\n",
    "                    cnt[y][0][w] = 1\n",
    "                    depth[y] = depth[x] + 1\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "\n",
    "        for i in range(m - 1):\n",
    "            for j in range(n):\n",
    "                p = pa[j][i]\n",
    "                if p != -1:\n",
    "                    pa[j][i + 1] = pa[p][i]\n",
    "                    for k in range(26):\n",
    "                        cnt[j][i + 1][k] += cnt[j][i][k] + cnt[p][i][k]\n",
    "        \n",
    "        ans = []\n",
    "        for x, y in queries:\n",
    "            path_len = depth[x] + depth[y]\n",
    "            c = [0] * 26\n",
    "            if depth[x] > depth[y]: x, y = y, x\n",
    "            k = depth[y] - depth[x]\n",
    "            for i in range(k.bit_length()):\n",
    "                if k >> i & 1:\n",
    "                    for j in range(26):\n",
    "                        c[j] += cnt[y][i][j]\n",
    "                    y = pa[y][i]\n",
    "\n",
    "            if x != y:\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    px, py = pa[x][i], pa[y][i]\n",
    "                    if px != py:\n",
    "                        for j in range(26):\n",
    "                            c[j] += cnt[x][i][j] + cnt[y][i][j]\n",
    "                        x, y = px, py\n",
    "                for j in range(26):\n",
    "                    c[j] += cnt[x][0][j] + cnt[y][0][j]\n",
    "                x = pa[x][0]\n",
    "            \n",
    "            ans.append(path_len - 2 * depth[x] - max(c))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "假设 lca 表示 [a, b] 两节点的最近公共祖先，那么 需要求出 [a, lca] 每条边出现的次数\n",
    "和 [b, lca] 每条边出现的次数，合并求出最多的次数，假设为 x, 求出 a 到 0(根节点) 有多少边 = depth[a]，和 b 到 0 有多少边 = depth[b]，答案就是 depth[a] + depth[b] - 2depth[lca] - x 就是需要调整的边\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b, w in edges:\n",
    "            graph[a].append((b, w - 1))\n",
    "            graph[b].append((a, w - 1))\n",
    "        m = n.bit_length()\n",
    "        pa = [[-1] * m for _ in range(n)]\n",
    "        # p = pa[x][0]: x 的父节点 = p\n",
    "        # pa[x][1] = pa[p][0]: x 爷爷节点 = p 的父节点\n",
    "        # pa[x][i] = 的 2^i 个父节点的位置 = pa[pa[x][i - 1]][i - 1]\n",
    "        depth = [0] * n\n",
    "        # cnt[x][i][w]: x 的 2^i 个父节点 和 x x 的 2^（i-1) 个父节点\n",
    "        cnt = [[[0] * 26 for _ in range(m)] for _ in range(n)]\n",
    "        def dfs(u: int, fa: int) -> int:\n",
    "            pa[u][0] = fa\n",
    "            for v,w in graph[u]:\n",
    "                if v != fa:\n",
    "                    cnt[v][0][w] = 1\n",
    "                    depth[v] = depth[u] + 1\n",
    "                    dfs(v, u)\n",
    "        dfs(0, -1)\n",
    "        for i in range(m - 1):\n",
    "            for x in range(n):\n",
    "                p = pa[x][i]\n",
    "                if p != -1:\n",
    "                    pa[x][i + 1] = pa[p][i]\n",
    "                    for j, (c1, c2) in enumerate(zip(cnt[x][i], cnt[p][i])):\n",
    "                        cnt[x][i + 1][j] = c1 + c2\n",
    "        ans = []\n",
    "        for (x, y) in queries:\n",
    "            path_len = depth[x] + depth[y]\n",
    "            #print(path_len)\n",
    "            # x -> y，w 出现的次数\n",
    "            cw = [0] * 26\n",
    "            if depth[x] > depth[y]:\n",
    "                x, y = y, x\n",
    "            # 获取 lca\n",
    "            k = depth[y] - depth[x]\n",
    "            for i in range(k.bit_length()):\n",
    "                if (1 << i) & k:\n",
    "                    for j, w in enumerate(cnt[y][i]):\n",
    "                        cw[j] += w\n",
    "                    y = pa[y][i]\n",
    "            if x != y:\n",
    "                # x, y 一起向上跳，找到 lca\n",
    "                for c in range(m - 1, -1, -1):\n",
    "                    if pa[x][c] != pa[y][c]:\n",
    "                        for i, (w1, w2) in enumerate(zip(cnt[x][c], cnt[y][c])):\n",
    "                            cw[i] += w1 + w2\n",
    "                        x, y = pa[x][c], pa[y][c]\n",
    "                # 累加当前位置的值\n",
    "                for i, (w1, w2) in enumerate(zip(cnt[x][c], cnt[y][c])):\n",
    "                    cw[i] += w1 + w2\n",
    "                x = pa[x][0]\n",
    "            lca = x\n",
    "            path_len -= depth[lca] * 2\n",
    "            # print(path_len, lca, cw)\n",
    "            # 减去出现次数最多的\n",
    "            ans.append(path_len - max(cw))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "找lca与dfs算法可以分开,先dfs，顺便计算depth[i]\n",
    "'''\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        depth=[0]*n\n",
    "        g=[[] for _ in range(n)]\n",
    "        #不会，remake-->正确做法，用元组\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w-1))\n",
    "            g[y].append((x,w-1))\n",
    "        #可以在计算路径长度的同时计算路径上字符出现次数？\n",
    "\n",
    "        #在dfs的过程中需要先确定父子关系\n",
    "        #预处理lca\n",
    "        \n",
    "        #初始化不会\n",
    "        m=n.bit_length()#集合二进制长度,最多用2<<m就会超过,所以最多只需要计算到2<<(m-1)\n",
    "        \n",
    "        #为了计算路径上字符出现次数，同时加速每次查询时间，我们也需要树上倍增算法\n",
    "        cnt=[[[0]*26 for _ in range(m)] for _ in range(n)]\n",
    "        pa=[[-1]*m for _ in range(n)]\n",
    "\n",
    "        def dfs(x:int,fa:int)->None:\n",
    "            pa[x][0]=fa\n",
    "            for y,w in g[x]:\n",
    "                if y!=fa:\n",
    "                    cnt[y][0][w]=1\n",
    "                    depth[y]=depth[x]+1\n",
    "                    dfs(y,x)\n",
    "        dfs(0,-1) \n",
    "\n",
    "        #pa[x][i+1]=pa[pa[x][i]][i],就是个很简单的dp\n",
    "\n",
    "        #倍增写的不太对\n",
    "        for i in range(m-1):\n",
    "            for x in range(n):\n",
    "                #没有考虑到pa[x][i]=-1的情况\n",
    "                p=pa[x][i]\n",
    "                if p!=-1:\n",
    "                    pp=pa[p][i]\n",
    "                    pa[x][i+1]=pp\n",
    "                    for c in range(26):\n",
    "                        cnt[x][i+1][c]=cnt[x][i][c]+cnt[p][i][c]\n",
    "\n",
    "                        \n",
    "        ans=[0]*len(queries)\n",
    "\n",
    "        for idx,(x,y) in enumerate(queries):\n",
    "            cw=[0]*26#计算路径上每种字符出现次数\n",
    "            path_len=depth[x]+depth[y]\n",
    "            if depth[x]>depth[y]:\n",
    "                x,y=y,x\n",
    "            k=depth[y]-depth[x]\n",
    "            for i in range(k.bit_length()):\n",
    "                if k>>i&1:\n",
    "                    p=pa[y][i]\n",
    "                    for c in range(26):\n",
    "                        cw[c]+=cnt[y][i][c]\n",
    "                    y=p\n",
    "\n",
    "            #当成二分来理解\n",
    "            if y!=x:\n",
    "                for i in range(m-1,-1,-1):\n",
    "                    px,py=pa[x][i],pa[y][i]\n",
    "                    if px!=py:\n",
    "                        for c in range(26):\n",
    "                            cw[c]+=(cnt[x][i][c]+cnt[y][i][c])\n",
    "                        x,y=px,py #同时向上跳2^i步\n",
    "                #最后还要再跳一步\n",
    "                for c in range(26):\n",
    "                    cw[c]+=(cnt[x][0][c]+cnt[y][0][c])\n",
    "                x=pa[x][0]\n",
    "            lca=x\n",
    "            path_len-=depth[lca]*2\n",
    "            ans[idx]=path_len-max(cw)\n",
    "        return ans\n",
    "    \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c - 1])\n",
    "            graph[b].append([a, c - 1])\n",
    "        m = n.bit_length()\n",
    "        pa = [[p] + [-1] * (m - 1) for p in range(n)]\n",
    "        counter = [[[0] * 26 for _ in range(m)] for _ in range(n)]\n",
    "        depth = [0] * n \n",
    "        def dfs(node, par):\n",
    "            for nei, w in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue  \n",
    "                depth[nei] = depth[node] + 1 \n",
    "                pa[nei][0] = node  \n",
    "                counter[nei][0][w] = 1 \n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        for i in range(m - 1):\n",
    "            for x in range(n):\n",
    "                p = pa[x][i]\n",
    "                pp = pa[p][i]\n",
    "                if pp != - 1:\n",
    "                    pa[x][i + 1] = pp      \n",
    "                    for j, (c1, c2) in enumerate(zip(counter[x][i], counter[p][i])):\n",
    "                        counter[x][i + 1][j] = c1 + c2 \n",
    "        \n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            path = depth[x] + depth[y]\n",
    "            if depth[x] > depth[y]:\n",
    "                x, y = y, x\n",
    "            k = depth[y] - depth[x]\n",
    "            cnt = [0] * 26\n",
    "            for i in range(k.bit_length()):\n",
    "                if k & 1 << i:\n",
    "                    p = pa[y][i]\n",
    "                    for j, c in enumerate(counter[y][i]):\n",
    "                        cnt[j] += c \n",
    "                    y = p \n",
    "            if x != y:\n",
    "                for i in range(m - 1, - 1, - 1):\n",
    "                    px, py = pa[x][i], pa[y][i]\n",
    "                    if px != py:\n",
    "                        for j, (c1, c2) in enumerate(zip(counter[x][i], counter[y][i])):\n",
    "                            cnt[j] += c1 + c2 \n",
    "                        x, y = px, py \n",
    "                for j, (c1, c2) in enumerate(zip(counter[x][0], counter[y][0])):\n",
    "                    cnt[j] += c1 + c2 \n",
    "                x = pa[x][0]\n",
    "            lca = x \n",
    "            path -= depth[lca] * 2 \n",
    "            res.append(path - max(cnt))\n",
    "        return res \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        m = n.bit_length()\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c - 1])\n",
    "            graph[b].append([a, c - 1])\n",
    "        depth = [0] * n  \n",
    "        pa = [[p] + [-1] * (m - 1) for p in range(n)]\n",
    "        counter = [[[0] * 26 for _ in range(m)] for _ in range(n)]\n",
    "        def dfs(node, parent):\n",
    "            for nei, w in graph[node]:\n",
    "                if nei == parent:\n",
    "                    continue\n",
    "                depth[nei] = depth[node] + 1 \n",
    "                pa[nei][0] = node  \n",
    "                counter[nei][0][w] = 1 \n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        # print(counter)\n",
    "        for i in range(m - 1):\n",
    "            for x in range(n):\n",
    "                p = pa[x][i]\n",
    "                pp = pa[p][i]\n",
    "                if pp != - 1:\n",
    "                    pa[x][i + 1] = pp   \n",
    "                    for j, (c1, c2) in enumerate(zip(counter[x][i], counter[p][i])):\n",
    "                        counter[x][i + 1][j] = c1 + c2 \n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            path = depth[x] + depth[y]\n",
    "            if depth[y] < depth[x]:\n",
    "                x, y = y, x \n",
    "            cnt = [0] * 26\n",
    "            k = depth[y] - depth[x]\n",
    "            for i in range(k.bit_length()):\n",
    "                if  k & 1 << i:\n",
    "                    p = pa[y][i]\n",
    "                    for j, c in enumerate(counter[y][i]):\n",
    "                        cnt[j] += c \n",
    "                    y = p \n",
    "            if x != y:\n",
    "                for i in range(m - 1, - 1, - 1):\n",
    "                    px, py = pa[x][i], pa[y][i] \n",
    "                    if px != py:\n",
    "                        for j, (c1, c2) in enumerate(zip(counter[x][i], counter[y][i])):\n",
    "                            cnt[j] += c1 + c2 \n",
    "                        x, y = px, py \n",
    "                for j, (c1, c2) in enumerate(zip(counter[x][0], counter[y][0])):\n",
    "                    cnt[j] += c1 + c2 \n",
    "                x = pa[x][0]\n",
    "            lca = x \n",
    "            path -= depth[lca] * 2 \n",
    "            res.append(path - max(cnt))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        m = n.bit_length()\n",
    "        parents = [[-1] * m for i in range(n)]\n",
    "        sons = [[] for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "\n",
    "        for u, v, w in edges:\n",
    "            sons[u].append((v, w - 1))\n",
    "            sons[v].append((u, w - 1))\n",
    "\n",
    "        weights = [[[0] * 26 for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "        def dfs(son: int, par: int) -> None:\n",
    "            parents[son][0] = par\n",
    "            for s, w in sons[son]:\n",
    "                if s != par:\n",
    "                    weights[s][0][w] = 1\n",
    "                    depth[s] = depth[son] + 1\n",
    "                    dfs(s, son)\n",
    "\n",
    "        dfs(0, -1)\n",
    "\n",
    "        for i in range(m - 1):\n",
    "            for s in range(n):\n",
    "                p = parents[s][i]\n",
    "                pp = parents[p][i]\n",
    "                parents[s][i + 1] = pp\n",
    "                for j, (ws, wp) in enumerate(zip(weights[s][i], weights[p][i])):\n",
    "                    weights[s][i + 1][j] += ws + wp\n",
    "\n",
    "        answer = []\n",
    "        for u, v in queries:\n",
    "            if depth[u] < depth[v]:\n",
    "                u, v = v, u\n",
    "            ans = depth[u] + depth[v]\n",
    "\n",
    "            w = [0] * 26\n",
    "            d = depth[u] - depth[v]\n",
    "            \n",
    "            for i in range(d.bit_length()):\n",
    "                if d >> i & 1:\n",
    "                    for j, dw in enumerate(weights[u][i]):\n",
    "                        w[j] += dw\n",
    "                    u = parents[u][i]\n",
    "            \n",
    "            if u != v:\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    pu, pv = parents[u][i], parents[v][i]\n",
    "                    if pu != pv:\n",
    "                        for j, (duw, dvw) in enumerate(zip(weights[u][i], weights[v][i])):\n",
    "                            w[j] += duw + dvw\n",
    "                        u = pu\n",
    "                        v = pv\n",
    "\n",
    "                for j, (duw, dvw) in enumerate(zip(weights[u][0], weights[v][0])):\n",
    "                    w[j] += duw + dvw\n",
    "\n",
    "            if u != v:\n",
    "                u = parents[u][0]\n",
    "            answer.append(ans - depth[u] * 2 - max(w))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        m = n.bit_length()\n",
    "        g = [[] for _ in range(n)]\n",
    "        pa = [[-1] * m for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "        cnt = [[[0] * 26 for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "        for x, y, w in edges:\n",
    "            g[x].append([y, w - 1])\n",
    "            g[y].append([x, w - 1])\n",
    "        \n",
    "        def dfs(x, fa):\n",
    "            pa[x][0] = fa\n",
    "            for y, w in g[x]:\n",
    "                if y != fa:\n",
    "                    depth[y] = depth[x] + 1\n",
    "                    cnt[y][0][w] = 1\n",
    "                    dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "\n",
    "        for i in range(m - 1):\n",
    "            for j in range(n):\n",
    "                p = pa[j][i]\n",
    "                if p == -1:\n",
    "                    continue\n",
    "                pp = pa[p][i]\n",
    "                pa[j][i + 1] = pp\n",
    "                for k, (c1, c2) in enumerate(zip(cnt[j][i], cnt[p][i])):\n",
    "                    cnt[j][i + 1][k] = c1 + c2\n",
    "        \n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            path_len = depth[x] + depth[y]\n",
    "            cw = [0] * 26\n",
    "\n",
    "            if depth[x] > depth[y]:\n",
    "                x, y = y, x\n",
    "            \n",
    "            k = depth[y] - depth[x]\n",
    "            for i in range(k.bit_length() - 1, -1, -1):\n",
    "                if (k >> i) & 1:\n",
    "                    for j, c in enumerate(cnt[y][i]):\n",
    "                        cw[j] += c\n",
    "                    y = pa[y][i]\n",
    "            \n",
    "            # 现在x和y同深度\n",
    "            if x == y:\n",
    "                lca = x\n",
    "            else:\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    px = pa[x][i]\n",
    "                    py = pa[y][i]\n",
    "                    if px != py:\n",
    "                        for j, (c1, c2) in enumerate(zip(cnt[x][i], cnt[y][i])):\n",
    "                            cw[j] += c1 + c2\n",
    "                        x, y = px, py\n",
    "                for j, (c1, c2) in enumerate(zip(cnt[x][0], cnt[y][0])):\n",
    "                    cw[j] += c1 + c2\n",
    "                lca = pa[x][0]\n",
    "\n",
    "            path_len -= 2 * depth[lca]\n",
    "            res.append(path_len - max(cw))\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        depths = [0] * n\n",
    "        m = n.bit_length()\n",
    "        weights = [[[0] * 26 for _ in range(m)] for _ in range(n)]\n",
    "        neighbours = [[] for _ in range(n)]\n",
    "        ancestors = [[-1] * m for _ in range(n)]\n",
    "        for f, t, w in edges:\n",
    "            neighbours[f].append([t,w - 1])\n",
    "            neighbours[t].append([f,w - 1])\n",
    "\n",
    "        def dfs(x:int, fa:int) -> int:\n",
    "            #ancestors[x][0] = fa\n",
    "            for y, w in neighbours[x]:\n",
    "                if y == fa:\n",
    "                    continue\n",
    "                depths[y] = depths[x] + 1\n",
    "                weights[y][0][w] += 1\n",
    "                ancestors[y][0] = x\n",
    "                dfs(y, x)\n",
    "        dfs(0, -1)\n",
    "        \n",
    "        for j in range(1, m):\n",
    "            for i in range(n):\n",
    "                p = ancestors[i][j - 1]\n",
    "                if p != -1:\n",
    "                    ancestors[i][j] = ancestors[p][j - 1]\n",
    "                    for idx,(w1,w2) in enumerate(zip(weights[i][j - 1], weights[p][j - 1])):\n",
    "                        weights[i][j][idx] = w1 + w2\n",
    "        #print(\"depths -\", depths)\n",
    "        #print(\"weights -\", weights[3])\n",
    "        ans = []\n",
    "        for f, t in queries:\n",
    "            #print(\"f -\", f, \"t -\", t)\n",
    "            path_len = depths[f] + depths[t]\n",
    "            if depths[f] < depths[t]:\n",
    "                f, t = t, f\n",
    "            qeury_weight = [0] * 26\n",
    "            if depths[f] != depths[t]:\n",
    "                k = depths[f] - depths[t]\n",
    "                p = f\n",
    "                for i in range(k.bit_length()):\n",
    "                    if (k >> i) & 1:\n",
    "                        for idx,w in enumerate(weights[p][i]):\n",
    "                            qeury_weight[idx] += w\n",
    "                        p = ancestors[p][i]\n",
    "                f = p\n",
    "            #print(\"revised:\", \"f -\", f, \"d -\", d)\n",
    "            #print(\"revised:\", \"qeury_weight -\", qeury_weight)\n",
    "            def get_lca(node1, node2):\n",
    "                if node1 == node2:\n",
    "                    return node1\n",
    "                \n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    p_node1 = ancestors[node1][i]\n",
    "                    p_node2 = ancestors[node2][i]\n",
    "                    if p_node1 != p_node2:\n",
    "                        for idx,(w1,w2) in enumerate(zip(weights[node1][i], weights[node2][i])):\n",
    "                            qeury_weight[idx] += w1 + w2\n",
    "                        node1,node2 = p_node1,p_node2\n",
    "                for idx,(w1,w2) in enumerate(zip(weights[node1][0], weights[node2][0])):\n",
    "                    qeury_weight[idx] += w1 + w2\n",
    "                return ancestors[node1][0]\n",
    "            lca_node = get_lca(f, t)\n",
    "            #print(\"lca_node -\", lca_node)\n",
    "\n",
    "            path_len -= 2 * depths[lca_node]\n",
    "            #print(\"path_len -\", path_len)\n",
    "            #print(\"qeury_weight -\", qeury_weight)\n",
    "            ans.append(path_len - max(qeury_weight))\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        # 求lca 两点最近祖先，然后求点到祖先各个权重边出现的次数，最后边数量-出现最多的次数即为答案\n",
    "        graph = DefaultDict(lambda: DefaultDict(int))\n",
    "        for u, v, w in edges:\n",
    "            graph[u][v] = w\n",
    "            graph[v][u] = w\n",
    "        pa = [-1]*n\n",
    "        dep = [0]*n\n",
    "\n",
    "        m = n.bit_length()-1\n",
    "        cnt = [[[0]*27 for _ in range(m+1)] for _ in range(n)]\n",
    "\n",
    "        def dfs(x, fa, d):\n",
    "            pa[x] = fa\n",
    "            dep[x] = d\n",
    "            for v, w in graph[x].items():\n",
    "\n",
    "                if v == fa:\n",
    "                    continue\n",
    "                # v节点到2^0 个父节点 权重为w的边数量+1\n",
    "                cnt[v][0][w] += 1\n",
    "                dfs(v, x, d+1)\n",
    "        dfs(0, -1, 0)\n",
    "\n",
    "        fa = [[p]+[-1]*m for p in pa]\n",
    "\n",
    "        # 倍增预处理\n",
    "        for j in range(m):\n",
    "            for i in range(n):\n",
    "                if fa[i][j] != -1:\n",
    "                    pi = fa[i][j]\n",
    "                    fa[i][j+1] = fa[pi][j]\n",
    "                    # 枚举26种边的权值\n",
    "                    for w in range(1, 27):\n",
    "                        # v节点到2^j+1 个父节点 权重为w的边数量+1\n",
    "                        cnt[i][j+1][w] = cnt[i][j][w]+cnt[pi][j][w]\n",
    "\n",
    "        def get_kth_ancestor(node, k, mc):\n",
    "            for i in range(k.bit_length()):\n",
    "                if (k >> i) & 1:\n",
    "                    # 26中边,每种\n",
    "                    for w in range(1, 27):\n",
    "                        mc[w] += cnt[node][i][w]\n",
    "                    node = fa[node][i]\n",
    "            return node\n",
    "\n",
    "        def lca(x, y):\n",
    "            if dep[x] > dep[y]:\n",
    "                x, y = y, x\n",
    "            mc = [0]*27\n",
    "            y = get_kth_ancestor(y, dep[y]-dep[x], mc)\n",
    "            if y != x:\n",
    "                for i in range(m-1,-1,-1):\n",
    "                    px, py = fa[x][i], fa[y][i]\n",
    "                    if px != py:\n",
    "                        for w in range(1, 27):\n",
    "                            mc[w] += cnt[x][i][w] + cnt[y][i][w]\n",
    "                        x, y = px, py\n",
    "                for w in range(1, 27):\n",
    "                    mc[w] += cnt[x][0][w]+cnt[y][0][w]\n",
    "            return mc\n",
    "\n",
    "        ret = []\n",
    "        for x, y in queries:\n",
    "            mc = lca(x, y)\n",
    "            ret.append(sum(mc)-max(mc))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c - 1])\n",
    "            graph[b].append([a, c - 1])\n",
    "        m = n.bit_length()\n",
    "        pa = [[-1 for _ in range(m)] for _ in range(n)]\n",
    "        counter = [[[0 for _ in range(26)] for _ in range(m)] for _ in range(n)]\n",
    "        depth = [0] * n\n",
    "        def dfs(node, parent):\n",
    "            for nei, w in graph[node]:\n",
    "                if nei == parent:\n",
    "                    continue\n",
    "                depth[nei] = depth[node] + 1 \n",
    "                pa[nei][0] = node\n",
    "                counter[nei][0][w] = 1 \n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        for i in range(m - 1):\n",
    "            for x in range(n):\n",
    "                p = pa[x][i]\n",
    "                pp = pa[p][i]\n",
    "                if pp != - 1:\n",
    "                    pa[x][i + 1] = pp\n",
    "                    for j, (c1, c2) in enumerate(zip(counter[x][i], counter[p][i])):\n",
    "                        counter[x][i + 1][j] = c1 + c2 \n",
    "        \n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            path_len = depth[x] + depth[y]\n",
    "            cnt = [0] * 26 \n",
    "            if depth[x] > depth[y]:\n",
    "                x, y = y, x \n",
    "            k = depth[y] - depth[x]\n",
    "            for i in range(k.bit_length()):\n",
    "                if k & 1 << i:\n",
    "                    p = pa[y][i]\n",
    "                    for j, c in enumerate(counter[y][i]):\n",
    "                        cnt[j] += c\n",
    "                    y = p\n",
    "            if x != y:\n",
    "                for i in range(m - 1, - 1, - 1):\n",
    "                    px, py = pa[x][i], pa[y][i]\n",
    "                    if px != py:\n",
    "                        for j, (c1, c2) in enumerate(zip(counter[x][i], counter[y][i])):\n",
    "                            cnt[j] += c1 + c2 \n",
    "                        x, y = px, py\n",
    "                for j, (c1, c2) in enumerate(zip(counter[x][0], counter[y][0])):\n",
    "                    cnt[j] += c1 + c2 \n",
    "                x = pa[x][0]\n",
    "            lca = x \n",
    "            path_len -= depth[lca] * 2 \n",
    "            res.append(path_len - max(cnt))\n",
    "        return res  \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        m = n.bit_length()\n",
    "        fa = [[-1 for i in range(m)] for j in range(n)]\n",
    "        cnt = [[[0 for i in range(26)] for j in range(m)] for k in range(n)]\n",
    "\n",
    "        G = [[] for i in range(n)]\n",
    "\n",
    "        depth = [0 for i in range(n)]\n",
    "\n",
    "        for edge in edges:\n",
    "            u, v, w = edge\n",
    "            G[u].append((v, w - 1))\n",
    "            G[v].append((u, w - 1))\n",
    "\n",
    "        def dfs(u: int, f: int):\n",
    "            fa[u][0] = f\n",
    "            for ele in G[u]:\n",
    "                v, w = ele\n",
    "                if v == f:\n",
    "                    continue\n",
    "                depth[v] = depth[u] + 1\n",
    "                \n",
    "                cnt[v][0][w] += 1 \n",
    "                dfs(v, u)\n",
    "\n",
    "        \n",
    "        dfs(0, -1)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        for j in range(1, m):\n",
    "            for i in range(n):\n",
    "                p = fa[i][j - 1]\n",
    "                if p == -1:\n",
    "                    continue\n",
    "                fa[i][j] = fa[p][j - 1]\n",
    "                # print(\"j = {}, i = {}, p = {}\".format(j, i, p))\n",
    "                for k, (l, r) in enumerate(zip(cnt[i][j - 1], cnt[p][j - 1])):\n",
    "                    cnt[i][j][k] = l + r\n",
    "\n",
    "        # print(fa)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for query in queries:\n",
    "            u, v = query\n",
    "            path_len = depth[u] + depth[v]\n",
    "\n",
    "            cntw = [0 for i in range(26)]\n",
    "            \n",
    "            if depth[u] > depth[v]:\n",
    "                u, v = v, u\n",
    "\n",
    "            k = depth[v] - depth[u]\n",
    "\n",
    "\n",
    "            for i in range(k.bit_length()):\n",
    "                # print(\"k = {}, (k >> i) & 1 = {}, i = {}\".format(k, (k >> i) & 1, i))\n",
    "                if (k >> i) & 1:\n",
    "                    y = fa[v][i]\n",
    "                    for j, val in enumerate(cnt[v][i]):\n",
    "                        cntw[j] += val\n",
    "                    v = y\n",
    "\n",
    "            # print(\"u = {}, v = {}\".format(u, v))\n",
    "\n",
    "\n",
    "            if u != v:\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    fu, fv = fa[u][i], fa[v][i]\n",
    "                    if fu != fv:\n",
    "                        for j, (c1, c2) in enumerate(zip(cnt[u][i], cnt[v][i])):\n",
    "                            cntw[j] += c1 + c2\n",
    "                        u, v = fu, fv\n",
    "\n",
    "                for j, (c1, c2) in enumerate(zip(cnt[u][0], cnt[v][0])):\n",
    "                    cntw[j] += c1 + c2\n",
    "                u = fa[u][0]\n",
    "            \n",
    "            lca = u\n",
    "            # print(\"lca = {}\".format(lca))\n",
    "            path_len -= depth[lca] * 2\n",
    "            ans.append(path_len - max(cntw))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
